Weired Algorithm

CSES - Weird Algorithm Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:
3105168421

Your task is to simulate the execution of the algorithm for a given value of n.

Input

The only input line contains an integer n.

Output

Print a line that contains all values of n during the algorithm.

Constraints
Example

Input:
3

Output:
3 10 5 16 8 4 2 1

Missing Number

CSES - Missing Number You are given all numbers between 1,2,,n except one. Your task is to find the missing number.

Input

The first input line contains an integer n.

The second line contains n1 numbers. Each number is distinct and between 1 and n (inclusive).

Output

Print the missing number.

Constraints
Example

Input:
5
2 3 1 5


Output:
4

Repetitions

CSES - Repetitions You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence. This is a maximum-length substring containing only one type of character.

Input

The only input line contains a string of n characters.

Output

Print one integer: the length of the longest repetition.

Constraints
Example

Input:
ATTCGGGA

Output:
3

Increasing Array

CSES - Increasing Array You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.

On each move, you may increase the value of any element by one. What is the minimum number of moves required?

Input

The first input line contains an integer n: the size of the array.

Then, the second line contains n integers x1,x2,,xn: the contents of the array.

Output

Print the minimum number of moves.

Constraints
Example

Input:
5
3 2 5 1 7


Output:
5

Permutations

CSES - Permutations A permutation of integers 1,2,,n is called beautiful if there are no adjacent elements whose difference is 1.

Given n, construct a beautiful permutation if such a permutation exists.

Input

The only input line contains an integer n.

Output

Print a beautiful permutation of integers 1,2,,n. If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".

Constraints
Example 1

Input:
5

Output:
4 2 5 3 1

Example 2

Input:
3

Output:
NO SOLUTION

Number Spiral

CSES - Number Spiral A number spiral is an infinite grid whose upper-left square has number 1. Here are the first five layers of the spiral:

Your task is to find out the number in row y and column x.

Input

The first input line contains an integer t: the number of tests.

After this, there are t lines, each containing integers y and x.

Output

For each test, print the number in row y and column x.

Constraints
Example

Input:
3
2 3
1 1
4 2


Output:
8
1
15

CSES - Two Knights Your task is to count for k=1,2,,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other.

Input

The only input line contains an integer n.

Output

Print n integers: the results.

Constraints
Example

Input:
8

Output:
0
6
28
96
252
550
1056
1848

CSES - Two Sets Your task is to divide the numbers 1,2,,n into two sets of equal sum.

Input

The only input line contains an integer n.

Output

Print "YES", if the division is possible, and "NO" otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

Constraints
Example 1

Input:
7

Output:
YES
4
1 2 4 7
3
3 5 6


Example 2

Input:
6

Output:
NO

Bit Strings

CSES - Bit Strings Your task is to calculate the number of bit strings of length n.

For example, if n=3, the correct answer is 8, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.

Input

The only input line has an integer n.

Output

Print the result modulo 109+7.

Constraints
Example

Input:
3

Output:
8

Trailing Zeroes

CSES - Trailing Zeros Your task is to calculate the number of trailing zeros in the factorial n!.

For example, 20!=2432902008176640000 and it has 4 trailing zeros.

Input

The only input line has an integer n.

Output

Print the number of trailing zeros in n!.

Constraints
Example

Input:
20

Output:
4

Coin Piles

CSES - Coin Piles You have two coin piles containing a and b coins. On each move, you can either remove one coin from the left pile and two coins from the right pile, or two coins from the left pile and one coin from the right pile.

Your task is to efficiently find out if you can empty both the piles.

Input

The first input line has an integer t: the number of tests.

After this, there are t lines, each of which has two integers a and b: the numbers of coins in the piles.

Output

For each test, print "YES" if you can empty the piles and "NO" otherwise.

Constraints
Example

Input:
3
2 1
2 2
3 3


Output:
YES
NO
YES

Palinderome Reorder

CSES - Palindrome Reorder Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (i.e., it reads the same forwards and backwards).

Input

The only input line has a string of length n consisting of characters A–Z.

Output

Print a palindrome consisting of the characters of the original string. You may print any valid solution. If there are no solutions, print "NO SOLUTION".

Constraints
Example

Input:
AAAACACBA

Output:
AACABACAA

Gray Code

CSES - Gray Code A Gray code is a list of all 2n bit strings of length n, where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).

Your task is to create a Gray code for a given length n.

Input

The only input line has an integer n.

Output

Print 2n lines that describe the Gray code. You can print any valid solution.

Constraints
Example

Input:
2

Output:
00
01
11
10

Tower of Hanoi

CSES - Gray Code A Gray code is a list of all 2n bit strings of length n, where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).

Your task is to create a Gray code for a given length n.

Input

The only input line has an integer n.

Output

Print 2n lines that describe the Gray code. You can print any valid solution.

Constraints
Example

Input:
2

Output:
00
01
11
10

Tower of Hanoi

CSES - Tower of Hanoi The Tower of Hanoi game consists of three stacks (left, middle and right) and n round disks of different sizes. Initially, the left stack has all the disks, in increasing order of size from top to bottom.

The goal is to move all the disks to the right stack using the middle stack. On each move you can move the uppermost disk from a stack to another stack. In addition, it is not allowed to place a larger disk on a smaller disk.

Your task is to find a solution that minimizes the number of moves.

Input

The only input line has an integer n: the number of disks.

Output

First print an integer k: the minimum number of moves.

After this, print k lines that describe the moves. Each line has two integers a and b: you move a disk from stack a to stack b.

Constraints
Example

Input:
2

Output:
3
1 2
1 3
2 3

Creating Strings

CSES - Creating Strings Given a string, your task is to generate all different strings that can be created using its characters.

Input

The only input line has a string of length n. Each character is between a–z.

Output

First print an integer k: the number of strings. Then print k lines: the strings in alphabetical order.

Constraints
Example

Input:
aabac

Output:
20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa

Apple Division

CSES - Apple Division There are n apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

Input

The first input line has an integer n: the number of apples.

The next line has n integers p1,p2,,pn: the weight of each apple.

Output

Print one integer: the minimum difference between the weights of the groups.

Constraints
Example

Input:
5
3 2 7 4 1


Output:
1

Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8).

Chessboard and Queens

CSES - Chessboard and Queens Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking each other.

How many possible ways are there to place the queens?

Input

The input has eight lines, and each of them has eight characters. Each square is either free (.) or reserved (*).

Output

Print one integer: the number of ways you can place the queens.

Example

Input:
........
........
..*.....
........
........
.....**.
...*....
........


Output:
65

Digit Queries

CSES - Digit Queries Consider an infinite string that consists of all positive integers in increasing order:

12345678910111213141516171819202122232425...

Your task is to process q queries of the form: what is the digit at position k in the string?

Input

The first input line has an integer q: the number of queries.

After this, there are q lines that describe the queries. Each line has an integer k: a 1-indexed position in the string.

Output

For each query, print the corresponding digit.

Constraints
Example

Input:
3
7
19
12


Output:
7
4
1

Grid Paths

CSES - Grid Paths There are 88418 paths in a 7×7 grid from the upper-left square to the lower-left square. Each path corresponds to a 48-character description consisting of characters D (down), U (up), L (left) and R (right).

For example, the path

corresponds to the description DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD.

You are given a description of a path which may also contain characters ? (any direction). Your task is to calculate the number of paths that match the description.

Input

The only input line has a 48-character string of characters ?, D, U, L and R.

Output

Print one integer: the total number of paths.

Example

Input:
??????R??????U??????????????????????????LD????D?

Output:
201


Sorting and Searching



Distinct Numbers

CSES - Distinct Numbers You are given a list of n integers, and your task is to calculate the number of distinct values in the list.

Input

The first input line has an integer n: the number of values.

The second line has n integers x1,x2,,xn.

Output

Print one integers: the number of distinct values.

Constraints
Example

Input:
5
2 3 2 2 3


Output:
2

Apartments

CSES - Apartments There are n applicants and m free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.

Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.

Input

The first input line has three integers n, m, and k: the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains n integers a1,a2,,an: the desired apartment size of each applicant. If the desired size of an applicant is x, he or she will accept any apartment whose size is between xk and x+k.

The last line contains m integers b1,b2,,bm: the size of each apartment.

Output

Print one integer: the number of applicants who will get an apartment.

Constraints
Example

Input:
4 3 5
60 45 80 60
30 60 75


Output:
2

Ferris Wheel

CSES - Ferris Wheel There are n children who want to go to a Ferris wheel, and your task is to find a gondola for each child.

Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed x. You know the weight of every child.

What is the minimum number of gondolas needed for the children?

Input

The first input line contains two integers n and x: the number of children and the maximum allowed weight.

The next line contains n integers p1,p2,,pn: the weight of each child.

Output

Print one integer: the minimum number of gondolas.

Constraints
Example

Input:
4 10
7 2 3 9


Output:
3

Concert Tickets

CSES - Concert Tickets There are n concert tickets available, each with a certain price. Then, m customers arrive, one after another.

Each customer announces the maximum price they are willing to pay for a ticket, and after this, they will get a ticket with the nearest possible price such that it does not exceed the maximum price.

Input

The first input line contains integers n and m: the number of tickets and the number of customers.

The next line contains n integers h1,h2,,hn: the price of each ticket.

The last line contains m integers t1,t2,,tm: the maximum price for each customer in the order they arrive.

Output

Print, for each customer, the price that they will pay for their ticket. After this, the ticket cannot be purchased again.

If a customer cannot get any ticket, print 1.

Constraints
Example

Input:
5 3
5 3 7 8 5
4 8 3


Output:
3
8
-1

Restaurant Customers

CSES - Restaurant Customers You are given the arrival and leaving times of n customers in a restaurant.

What was the maximum number of customers in the restaurant at any time?

Input

The first input line has an integer n: the number of customers.

After this, there are n lines that describe the customers. Each line has two integers a and b: the arrival and leaving times of a customer.

You may assume that all arrival and leaving times are distinct.

Output

Print one integer: the maximum number of customers.

Constraints
Example

Input:
3
5 8
2 4
3 9


Output:
2

Movie Festival

CSES - Movie Festival In a movie festival n movies will be shown. You know the starting and ending time of each movie. What is the maximum number of movies you can watch entirely?

Input

The first input line has an integer n: the number of movies.

After this, there are n lines that describe the movies. Each line has two integers a and b: the starting and ending times of a movie.

Output

Print one integer: the maximum number of movies.

Constraints
Example

Input:
3
3 5
4 9
5 8


Output:
2

Sum of Two Values

CSES - Sum of Two Values You are given an array of n integers, and your task is to find two values (at distinct positions) whose sum is x.

Input

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a1,a2,,an: the array values.

Output

Print two integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

Constraints
Example

Input:
4 8
2 7 5 1


Output:
2 4

Maximum Subarray Sum

CSES - Maximum Subarray Sum Given an array of n integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.

Input

The first input line has an integer n: the size of the array.

The second line has n integers x1,x2,,xn: the array values.

Output

Print one integer: the maximum subarray sum.

Constraints
Example

Input:
8
-1 3 -2 5 3 -5 2 2


Output:
9

Stick Lengths

CSES - Stick Lengths There are n sticks with some lengths. Your task is to modify the sticks so that each stick has the same length.

You can either lengthen and shorten each stick. Both operations cost x where x is the difference between the new and original length.

What is the minimum total cost?

Input

The first input line contains an integer n: the number of sticks.

Then there are n integers: p1,p2,,pn: the lengths of the sticks.

Output

Print one integer: the minimum total cost.

Constraints
Example

Input:
5
2 3 1 5 2


Output:
5

Missing Coin Sum

CSES - Missing Coin Sum You have n coins with positive integer values. What is the smallest sum you cannot create using a subset of the coins?

Input

The first input line has an integer n: the number of coins.

The second line has n integers x1,x2,,xn: the value of each coin.

Output

Print one integer: the smallest coin sum.

Constraints
Example

Input:
5
2 9 1 2 7


Output:
6

Collecting NUmbers

CSES - Collecting Numbers You are given an array that contains each number between 1n exactly once. Your task is to collect the numbers from 1 to n in increasing order.

On each round, you go through the array from left to right and collect as many numbers as possible. What will be the total number of rounds?

Input

The first line has an integer n: the array size.

The next line has n integers x1,x2,,xn: the numbers in the array.

Output

Print one integer: the number of rounds.

Constraints
Example

Input:
5
4 2 1 5 3


Output:
3

Collecting Numbers II

CSES - Collecting Numbers II You are given an array that contains each number between 1n exactly once. Your task is to collect the numbers from 1 to n in increasing order.

On each round, you go through the array from left to right and collect as many numbers as possible.

Given m operations that swap two numbers in the array, your task is to report the number of rounds after each operation.

Input

The first line has two integers n and m: the array size and the number of operations.

The next line has n integers x1,x2,,xn: the numbers in the array.

Finally, there are m lines that describe the operations. Each line has two integers a and b: the numbers at positions a and b are swapped.

Output

Print m integers: the number of rounds after each swap.

Constraints
Example

Input:
5 3
4 2 1 5 3
2 3
1 5
2 3


Output:
2
3
4

PLaylist

CSES - Playlist You are given a playlist of a radio station since its establishment. The playlist has a total of n songs.

What is the longest sequence of successive songs where each song is unique?

Input

The first input line contains an integer n: the number of songs.

The next line has n integers k1,k2,,kn: the id number of each song.

Output

Print the length of the longest sequence of unique songs.

Constraints
Example

Input:
8
1 2 1 3 2 7 4 2


Output:
5

Towers

CSES - Towers You are given n cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower, or begin a new tower. What is the minimum possible number of towers?

Input

The first input line contains an integer n: the number of cubes.

The next line contains n integers k1,k2,,kn: the sizes of the cubes.

Output

Print one integer: the minimum number of towers.

Constraints
Example

Input:
5
3 8 2 1 5


Output:
2

Traffic Lights

CSES - Traffic Lights There is a street of length x whose positions are numbered 0,1,,x. Initially there are no traffic lights, but n sets of traffic lights are added to the street one after another.

Your task is to calculate the length of the longest passage without traffic lights after each addition.

Input

The first input line contains two integers x and n: the length of the street and the number of sets of traffic lights.

Then, the next line contains n integers p1,p2,,pn: the position of each set of traffic lights. Each position is distinct.

Output

Print the length of the longest passage without traffic lights after each addition.

Constraints
Example

Input:
8 3
3 6 2


Output:
5 3 3

Joshephus Problem I

CSES - Josephus Problem I Consider a game where there are n children (numbered 1,2,,n) in a circle. During the game, every second child is removed from the circle, until there are no children left. In which order will the children be removed?

Input

The only input line has an integer n.

Output

Print n integers: the removal order.

Constraints
Example

Input:
7

Output:
2 4 6 1 5 3 7

Joshephus Problem II

CSES - Josephus Problem II Consider a game where there are n children (numbered 1,2,,n) in a circle. During the game, repeatedly k children are skipped and one child is removed from the circle. In which order will the children be removed?

Input

The only input line has two integers n and k.

Output

Print n integers: the removal order.

Constraints
Example

Input:
7 2

Output:
3 6 2 7 5 1 4

Nested Ranges Check

CSES - Nested Ranges Check Given n ranges, your task is to determine for each range if it contains some other range and if some other range contains it.

Range [a,b] contains range [c,d] if ac and db.

Input

The first input line has an integer n: the number of ranges.

After this, there are n lines that describe the ranges. Each line has two integers x and y: the range is [x,y].

You may assume that no range appears more than once in the input.

Output

First print a line that describes for each range (in the input order) if it contains some other range (1) or not (0).

Then print a line that describes for each range (in the input order) if some other range contains it (1) or not (0).

Constraints
Example

Input:
4
1 6
2 4
4 8
3 6


Output:
1 0 0 0
0 1 0 1

Nested Ranges Count

CSES - Nested Ranges Count Given n ranges, your task is to count for each range how many other ranges it contains and how many other ranges contain it.

Range [a,b] contains range [c,d] if ac and db.

Input

The first input line has an integer n: the number of ranges.

After this, there are n lines that describe the ranges. Each line has two integers x and y: the range is [x,y].

You may assume that no range appears more than once in the input.

Output

First print a line that describes for each range (in the input order) how many other ranges it contains.

Then print a line that describes for each range (in the input order) how many other ranges contain it.

Constraints
Example

Input:
4
1 6
2 4
4 8
3 6


Output:
2 0 0 0
0 1 0 1

Room Allocation

CSES - Room Allocation There is a large hotel, and n customers will arrive soon. Each customer wants to have a single room.

You know each customer's arrival and departure day. Two customers can stay in the same room if the departure day of the first customer is earlier than the arrival day of the second customer.

What is the minimum number of rooms that are needed to accommodate all customers? And how can the rooms be allocated?

Input

The first input line contains an integer n: the number of customers.

Then there are n lines, each of which describes one customer. Each line has two integers a and b: the arrival and departure day.

Output

Print first an integer k: the minimum number of rooms required.

After that, print a line that contains the room number of each customer in the same order as in the input. The rooms are numbered 1,2,,k. You can print any valid solution.

Constraints
Example

Input:
3
1 2
2 4
4 4


Output:
2
1 2 1

Factory Machines

CSES - Factory Machines A factory has n machines which can be used to make products. Your goal is to make a total of t products.

For each machine, you know the number of seconds it needs to make a single product. The machines can work simultaneously, and you can freely decide their schedule.

What is the shortest time needed to make t products?

Input

The first input line has two integers n and t: the number of machines and products.

The next line has n integers k1,k2,,kn: the time needed to make a product using each machine.

Output

Print one integer: the minimum time needed to make t products.

Constraints
Example

Input:
3 7
3 2 5


Output:
8

Explanation: Machine 1 makes two products, machine 2 makes four products and machine 3 makes one product.

Task and Deadlines

CSES - Tasks and Deadlines You have to process n tasks. Each task has a duration and a deadline, and you will process the tasks in some order one after another. Your reward for a task is df where d is its deadline and f is your finishing time. (The starting time is 0, and you have to process all tasks even if a task would yield negative reward.)

What is your maximum reward if you act optimally?

Input

The first input line has an integer n: the number of tasks.

After this, there are n lines that describe the tasks. Each line has two integers a and d: the duration and deadline of the task.

Output

Print one integer: the maximum reward.

Constraints
Example

Input:
3
6 10
8 15
5 12


Output:
2

Reading Books

CSES - Reading Books There are n books, and Kotivalo and Justiina are going to read them all. For each book, you know the time it takes to read it.

They both read each book from beginning to end, and they cannot read a book at the same time. What is the minimum total time required?

Input

The first input line has an integer n: the number of books.

The second line has n integers t1,t2,,tn: the time required to read each book.

Output

Print one integer: the minimum total time.

Constraints
Example

Input:
3
2 8 3


Output:
16

Sum Of Three Values

CSES - Sum of Three Values You are given an array of n integers, and your task is to find three values (at distinct positions) whose sum is x.

Input

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a1,a2,,an: the array values.

Output

Print three integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

Constraints
Example

Input:
4 8
2 7 5 1


Output:
1 3 4

Sum of Four Values

CSES - Sum of Four Values You are given an array of n integers, and your task is to find four values (at distinct positions) whose sum is x.

Input

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a1,a2,,an: the array values.

Output

Print four integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

Constraints
Example

Input:
8 15
3 2 5 8 1 3 2 3


Output:
2 4 6 7

Nearest Smaller Values

CSES - Nearest Smaller Values Given an array of n integers, your task is to find for each array position the nearest position to its left having a smaller value.

Input

The first input line has an integer n: the size of the array.

The second line has n integers x1,x2,,xn: the array values.

Output

Print n integers: for each array position the nearest position with a smaller value. If there is no such position, print 0.

Constraints
Example

Input:
8
2 5 1 4 8 3 2 5


Output:
0 1 0 3 4 3 3 7

Subarray Sums I

CSES - Subarray Sums I Given an array of n positive integers, your task is to count the number of subarrays having sum x.

Input

The first input line has two integers n and x: the size of the array and the target sum x.

The next line has n integers a1,a2,,an: the contents of the array.

Output

Print one integer: the required number of subarrays.

Constraints
Example

Input:
5 7
2 4 1 2 7


Output:
3

Subarray Sums II

CSES - Subarray Sums II Given an array of n integers, your task is to count the number of subarrays having sum x.

Input

The first input line has two integers n and x: the size of the array and the target sum x.

The next line has n integers a1,a2,,an: the contents of the array.

Output

Print one integer: the required number of subarrays.

Constraints
Example

Input:
5 7
2 -1 3 5 -2


Output:
2

Subarray Divisibility

CSES - Subarray Divisibility Given an array of n integers, your task is to count the number of subarrays where the sum of values is divisible by n.

Input

The first input line has an integer n: the size of the array.

The next line has n integers a1,a2,,an: the contents of the array.

Output

Print one integer: the required number of subarrays.

Constraints
Example

Input:
5
3 1 2 7 4


Output:
1

Subarray Distinct Values

CSES - Subarray Distinct Values Given an array of n integers, your task is to calculate the number of subarrays that have at most k distinct values.

Input

The first input line has two integers n and k.

The next line has n integers x1,x2,,xn: the contents of the array.

Output

Print one integer: the number of subarrays.

Constraints
Example

Input:
5 2
1 2 3 1 1


Output:
10

Array Division

CSES - Array Division You are given an array containing n positive integers.

Your task is to divide the array into k subarrays so that the maximum sum in a subarray is as small as possible.

Input

The first input line contains two integers n and k: the size of the array and the number of subarrays in the division.

The next line contains n integers x1,x2,,xn: the contents of the array.

Output

Print one integer: the maximum sum in a subarray in the optimal division.

Constraints
Example

Input:
5 3
2 4 7 3 5


Output:
8

Explanation: An optimal division is [2,4],[7],[3,5] where the sums of the subarrays are 6,7,8. The largest sum is the last sum 8.

Sliding Median

CSES - Sliding Median You are given an array of n integers. Your task is to calculate the median of each window of k elements, from left to right.

The median is the middle element when the elements are sorted. If the number of elements is even, there are two possible medians and we assume that the median is the smaller of them.

Input

The first input line contains two integers n and k: the number of elements and the size of the window.

Then there are n integers x1,x2,,xn: the contents of the array.

Output

Print nk+1 values: the medians.

Constraints
Example

Input:
8 3
2 4 3 5 8 1 2 1


Output:
3 4 5 5 2 1

Sliding Cost

CSES - Sliding Cost You are given an array of n integers. Your task is to calculate for each window of k elements, from left to right, the minimum total cost of making all elements equal.

You can increase or decrease each element with cost x where x is the difference between the new and the original value. The total cost is the sum of such costs.

Input

The first input line contains two integers n and k: the number of elements and the size of the window.

Then there are n integers x1,x2,,xn: the contents of the array.

Output

Output nk+1 values: the costs.

Constraints
Example

Input:
8 3
2 4 3 5 8 1 2 1


Output:
2 2 5 7 7 1

Movie Festival II

CSES - Movie Festival II In a movie festival, n movies will be shown. Syrjälä's movie club consists of k members, who will be all attending the festival.

You know the starting and ending time of each movie. What is the maximum total number of movies the club members can watch entirely if they act optimally?

Input

The first input line has two integers n and k: the number of movies and club members.

After this, there are n lines that describe the movies. Each line has two integers a and b: the starting and ending time of a movie.

Output

Print one integer: the maximum total number of movies.

Constraints
Example

Input:
5 2
1 5
8 10
3 6
2 5
6 9


Output:
4

Maximum Subarraysum II

CSES - Maximum Subarray Sum II Given an array of n integers, your task is to find the maximum sum of values in a contiguous subarray with length between a and b.

Input

The first input line has three integers n, a and b: the size of the array and the minimum and maximum subarray length.

The second line has n integers x1,x2,,xn: the array values.

Output

Print one integer: the maximum subarray sum.

Constraints
Example

Input:
8 1 2
-1 3 -2 5 3 -5 2 2


Output:
8


Dynamic Programming



Dice Combinations

CSES - Dice Combinations Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.

For example, if n=3, there are 4 ways: Input

The only input line has an integer n.

Output

Print the number of ways modulo 109+7.

Constraints
Example

Input:
3

Output:
4

Minimizing Coins

CSES - Minimizing Coins Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to produce a sum of money x using the available coins in such a way that the number of coins is minimal.

For example, if the coins are {1,5,7} and the desired sum is 11, an optimal solution is 5+5+1 which requires 3 coins.

Input

The first input line has two integers n and x: the number of coins and the desired sum of money.

The second line has n distinct integers c1,c2,,cn: the value of each coin.

Output

Print one integer: the minimum number of coins. If it is not possible to produce the desired sum, print 1.

Constraints
Example

Input:
3 11
1 5 7


Output:
3

Coin Combinations I

CSES - Coin Combinations I Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 8 ways: Input

The first input line has two integers n and x: the number of coins and the desired sum of money.

The second line has n distinct integers c1,c2,,cn: the value of each coin.

Output

Print one integer: the number of ways modulo 109+7.

Constraints
Example

Input:
3 9
2 3 5


Output:
8

Coin COmbinations II

CSES - Coin Combinations II Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways: Input

The first input line has two integers n and x: the number of coins and the desired sum of money.

The second line has n distinct integers c1,c2,,cn: the value of each coin.

Output

Print one integer: the number of ways modulo 109+7.

Constraints
Example

Input:
3 9
2 3 5


Output:
3

Removing Digits

CSES - Removing Digits You are given an integer n. On each step, you may subtract one of the digits from the number.

How many steps are required to make the number equal to 0?

Input

The only input line has an integer n.

Output

Print one integer: the minimum number of steps.

Constraints
Example

Input:
27

Output:
5

Explanation: An optimal solution is 2720181090.

Grid Paths

CSES - Grid Paths Consider an n×n grid whose squares may have traps. It is not allowed to move to a square with a trap.

Your task is to calculate the number of paths from the upper-left square to the lower-right square. You can only move right or down.

Input

The first input line has an integer n: the size of the grid.

After this, there are n lines that describe the grid. Each line has n characters: . denotes an empty cell, and * denotes a trap.

Output

Print the number of paths modulo 109+7.

Constraints
Example

Input:
4
....
.*..
...*
*...


Output:
3

Book Shop

CSES - Book Shop You are in a book shop which sells n different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.

Input

The first input line contains two integers n and x: the number of books and the maximum total price.

The next line contains n integers h1,h2,,hn: the price of each book.

The last line contains n integers s1,s2,,sn: the number of pages of each book.

Output

Print one integer: the maximum number of pages.

Constraints
Example

Input:
4 10
4 8 5 3
5 12 8 1


Output:
13

Explanation: You can buy books 1 and 3. Their price is 4+5=9 and the number of pages is 5+8=13.

Array Description

CSES - Array Description You know that an array has n integers between 1 and m, and the absolute difference between two adjacent values is at most 1.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

Input

The first input line has two integers n and m: the array size and the upper bound for each value.

The next line has n integers x1,x2,,xn: the contents of the array. Value 0 denotes an unknown value.

Output

Print one integer: the number of arrays modulo 109+7.

Constraints
Example

Input:
3 5
2 0 2


Output:
3

Explanation: The arrays [2,1,2], [2,2,2] and [2,3,2] match the description.

Counting Towers

CSES - Array Description You know that an array has n integers between 1 and m, and the absolute difference between two adjacent values is at most 1.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

Input

The first input line has two integers n and m: the array size and the upper bound for each value.

The next line has n integers x1,x2,,xn: the contents of the array. Value 0 denotes an unknown value.

Output

Print one integer: the number of arrays modulo 109+7.

Constraints
Example

Input:
3 5
2 0 2


Output:
3

Explanation: The arrays [2,1,2], [2,2,2] and [2,3,2] match the description.

Edit Distance

CSES - Edit Distance The edit distance between two strings is the minimum number of operations required to transform one string into the other.

The allowed operations are: For example, the edit distance between LOVE and MOVIE is 2, because you can first replace L with M, and then add I.

Your task is to calculate the edit distance between two strings.

Input

The first input line has a string that contains n characters between A–Z.

The second input line has a string that contains m characters between A–Z.

Output

Print one integer: the edit distance between the strings.

Constraints
Example

Input:
LOVE
MOVIE


Output:
2

Rectangle Cutting

CSES - Rectangle Cutting Given an a×b rectangle, your task is to cut it into squares. On each move you can select a rectangle and cut it into two rectangles in such a way that all side lengths remain integers. What is the minimum possible number of moves?

Input

The only input line has two integers a and b.

Output

Print one integer: the minimum number of moves.

Constraints
Example

Input:
3 5

Output:
3

Money Sums

CSES - Money Sums You have n coins with certain values. Your task is to find all money sums you can create using these coins.

Input

The first input line has an integer n: the number of coins.

The next line has n integers x1,x2,,xn: the values of the coins.

Output

First print an integer k: the number of distinct money sums. After this, print all possible sums in increasing order.

Constraints
Example

Input:
4
4 2 5 2


Output:
9
2 4 5 6 7 8 9 11 13

Removal Game

CSES - Removal Game There is a list of n numbers and two players who move alternately. On each move, a player removes either the first or last number from the list, and their score increases by that number. Both players try to maximize their scores.

What is the maximum possible score for the first player when both players play optimally?

Input

The first input line contains an integer n: the size of the list.

The next line has n integers x1,x2,,xn: the contents of the list.

Output

Print the maximum possible score for the first player.

Constraints
Example

Input:
4
4 5 1 3


Output:
8

Two Sets II

CSES - Two Sets II Your task is to count the number of ways numbers 1,2,,n can be divided into two sets of equal sum.

For example, if n=7, there are four solutions:
Input

The only input line contains an integer n.

Output

Print the answer modulo 109+7.

Constraints
Example

Input:
7

Output:
4

Increasing Subsequence

CSES - Increasing Subsequence You are given an array containing n integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.

A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.

Input

The first line contains an integer n: the size of the array.

After this there are n integers x1,x2,,xn: the contents of the array.

Output

Print the length of the longest increasing subsequence.

Constraints
Example

Input:
8
7 3 5 3 6 2 9 8


Output:
4

Increasing Subsequence

CSES - Increasing Subsequence You are given an array containing n integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.

A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.

Input

The first line contains an integer n: the size of the array.

After this there are n integers x1,x2,,xn: the contents of the array.

Output

Print the length of the longest increasing subsequence.

Constraints
Example

Input:
8
7 3 5 3 6 2 9 8


Output:
4

Increasing Subsquence

CSES - Increasing Subsequence You are given an array containing n integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.

A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.

Input

The first line contains an integer n: the size of the array.

After this there are n integers x1,x2,,xn: the contents of the array.

Output

Print the length of the longest increasing subsequence.

Constraints
Example

Input:
8
7 3 5 3 6 2 9 8


Output:
4

Projects

CSES - Projects There are n projects you can attend. For each project, you know its starting and ending days and the amount of money you would get as reward. You can only attend one project during a day.

What is the maximum amount of money you can earn?

Input

The first input line contains an integer n: the number of projects.

After this, there are n lines. Each such line has three integers ai, bi, and pi: the starting day, the ending day, and the reward.

Output

Print one integer: the maximum amount of money you can earn.

Constraints
Example

Input:
4
2 4 4
3 6 6
6 8 2
5 7 3


Output:
7

Elevator Rides

CSES - Elevator Rides There are n people who want to get to the top of a building which has only one elevator. You know the weight of each person and the maximum allowed weight in the elevator. What is the minimum number of elevator rides?

Input

The first input line has two integers n and x: the number of people and the maximum allowed weight in the elevator.

The second line has n integers w1,w2,,wn: the weight of each person.

Output

Print one integer: the minimum number of rides.

Constraints
Example

Input:
4 10
4 8 6 1


Output:
2

Counting Tilings

CSES - Counting Tilings Your task is to count the number of ways you can fill an n×m grid using 1×2 and 2×1 tiles.

Input

The only input line has two integers n and m.

Output

Print one integer: the number of ways modulo 109+7.

Constraints
Example

Input:
4 7

Output:
781

Counting Numbers

CSES - Counting Numbers Your task is to count the number of integers between a and b where no two adjacent digits are the same.

Input

The only input line has two integers a and b.

Output

Print one integer: the answer to the problem.

Constraints
Example

Input:
123 321

Output:
171


Graph Algorithms



Counting Rooms

CSES - Counting Rooms You are given a map of a building, and your task is to count the number of its rooms. The size of the map is n×m squares, and each square is either floor or wall. You can walk left, right, up, and down through the floor squares.

Input

The first input line has two integers n and m: the height and width of the map.

Then there are n lines of m characters describing the map. Each character is either . (floor) or # (wall).

Output

Print one integer: the number of rooms.

Constraints
Example

Input:
5 8
########
#..#...#
####.#.#
#..#...#
########


Output:
3

Labyrinth

CSES - Labyrinth You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.

Input

The first input line has two integers n and m: the height and width of the map.

Then there are n lines of m characters describing the labyrinth. Each character is . (floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.

Output

First print "YES", if there is a path, and "NO" otherwise.

If there is a path, print the length of the shortest such path and its description as a string consisting of characters L (left), R (right), U (up), and D (down). You can print any valid solution.

Constraints
Example

Input:
5 8
########
#.A#...#
#.##.#B#
#......#
########


Output:
YES
9
LDDRRRRRU

Building Roads

CSES - Building Roads Byteland has n cities, and m roads between them. The goal is to construct new roads so that there is a route between any two cities.

Your task is to find out the minimum number of roads required, and also determine which roads should be built.

Input

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,,n.

After that, there are m lines describing the roads. Each line has two integers a and b: there is a road between those cities.

A road always connects two different cities, and there is at most one road between any two cities.

Output

First print an integer k: the number of required roads.

Then, print k lines that describe the new roads. You can print any valid solution.

Constraints
Example

Input:
4 2
1 2
3 4


Output:
1
2 3

Message Route

CSES - Message Route Syrjälä's network has n computers and m connections. Your task is to find out if Uolevi can send a message to Maija, and if it is possible, what is the minimum number of computers on such a route.

Input

The first input line has two integers n and m: the number of computers and connections. The computers are numbered 1,2,,n. Uolevi's computer is 1 and Maija's computer is n.

Then, there are m lines describing the connections. Each line has two integers a and b: there is a connection between those computers.

Every connection is between two different computers, and there is at most one connection between any two computers.

Output

If it is possible to send a message, first print k: the minimum number of computers on a valid route. After this, print an example of such a route. You can print any valid solution.

If there are no routes, print "IMPOSSIBLE".

Constraints
Example

Input:
5 5
1 2
1 3
1 4
2 3
5 4


Output:
3
1 4 5

Building Teams

CSES - Building Teams There are n pupils in Uolevi's class, and m friendships between them. Your task is to divide the pupils into two teams in such a way that no two pupils in a team are friends. You can freely choose the sizes of the teams.

Input

The first input line has two integers n and m: the number of pupils and friendships. The pupils are numbered 1,2,,n.

Then, there are m lines describing the friendships. Each line has two integers a and b: pupils a and b are friends.

Every friendship is between two different pupils. You can assume that there is at most one friendship between any two pupils.

Output

Print an example of how to build the teams. For each pupil, print "1" or "2" depending on to which team the pupil will be assigned. You can print any valid team.

If there are no solutions, print "IMPOSSIBLE".

Constraints
Example

Input:
5 3
1 2
1 3
4 5


Output:
1 2 2 1 2

Round Trip

CSES - Round Trip Byteland has n cities and m roads between them. Your task is to design a round trip that begins in a city, goes through two or more other cities, and finally returns to the starting city. Every intermediate city on the route has to be distinct.

Input

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,,n.

Then, there are m lines describing the roads. Each line has two integers a and b: there is a road between those cities.

Every road is between two different cities, and there is at most one road between any two cities.

Output

First print an integer k: the number of cities on the route. Then print k cities in the order they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints
Example

Input:
5 6
1 3
1 2
5 3
1 5
2 4
4 5


Output:
4
3 5 1 3

Monsters

CSES - Monsters You and some monsters are in a labyrinth. When taking a step to some direction in the labyrinth, each monster may simultaneously take one as well. Your goal is to reach one of the boundary squares without ever sharing a square with a monster.

Your task is to find out if your goal is possible, and if it is, print a path that you can follow. Your plan has to work in any situation; even if the monsters know your path beforehand.

Input

The first input line has two integers n and m: the height and width of the map.

After this there are n lines of m characters describing the map. Each character is . (floor), # (wall), A (start), or M (monster). There is exactly one A in the input.

Output

First print "YES" if your goal is possible, and "NO" otherwise.

If your goal is possible, also print an example of a valid path (the length of the path and its description using characters D, U, L, and R). You can print any path, as long as its length is at most nm steps.

Constraints
Example

Input:
5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######


Output:
YES
5
RRDDR

Shortest Routes I

CSES - Shortest Routes I There are n cities and m flight connections between them. Your task is to determine the length of the shortest route from Syrjälä to every city.

Input

The first input line has two integers n and m: the number of cities and flight connections. The cities are numbered 1,2,,n, and city 1 is Syrjälä.

After that, there are m lines describing the flight connections. Each line has three integers a, b and c: a flight begins at city a, ends at city b, and its length is c. Each flight is a one-way flight.

You can assume that it is possible to travel from Syrjälä to all other cities.

Output

Print n integers: the shortest route lengths from Syrjälä to cities 1,2,,n.

Constraints
Example

Input:
3 4
1 2 6
1 3 2
3 2 3
1 3 4


Output:
0 5 2

Shortest Routes II

CSES - Shortest Routes II There are n cities and m roads between them. Your task is to process q queries where you have to determine the length of the shortest route between two given cities.

Input

The first input line has three integers n, m and q: the number of cities, roads, and queries.

Then, there are m lines describing the roads. Each line has three integers a, b and c: there is a road between cities a and b whose length is c. All roads are two-way roads.

Finally, there are q lines describing the queries. Each line has two integers a and b: determine the length of the shortest route between cities a and b.

Output

Print the length of the shortest route for each query. If there is no route, print 1 instead.

Constraints
Example

Input:
4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2


Output:
5
5
8
-1
3

High Score

CSES - High Score You play a game consisting of n rooms and m tunnels. Your initial score is 0, and each tunnel increases your score by x where x may be both positive or negative. You may go through a tunnel several times.

Your task is to walk from room 1 to room n. What is the maximum score you can get?

Input

The first input line has two integers n and m: the number of rooms and tunnels. The rooms are numbered 1,2,,n.

Then, there are m lines describing the tunnels. Each line has three integers a, b and x: the tunnel starts at room a, ends at room b, and it increases your score by x. All tunnels are one-way tunnels.

You can assume that it is possible to get from room 1 to room n.

Output

Print one integer: the maximum score you can get. However, if you can get an arbitrarily large score, print 1.

Constraints
Example

Input:
4 5
1 2 3
2 4 -1
1 3 -2
3 4 7
1 4 4


Output:
5

Flight Discount

CSES - Flight Discount Your task is to find a minimum-price flight route from Syrjälä to Metsälä. You have one discount coupon, using which you can halve the price of any single flight during the route. However, you can only use the coupon once.

Input

The first input line has two integers n and m: the number of cities and flight connections. The cities are numbered 1,2,,n. City 1 is Syrjälä, and city n is Metsälä.

After this there are m lines describing the flights. Each line has three integers a, b, and c: a flight begins at city a, ends at city b, and its price is c. Each flight is unidirectional.

You can assume that it is always possible to get from Syrjälä to Metsälä.

Output

Print one integer: the price of the cheapest route from Syrjälä to Metsälä.

When you use the discount coupon for a flight whose price is x, its price becomes x/2 (it is rounded down to an integer).

Constraints
Example

Input:
3 4
1 2 3
2 3 1
1 3 7
2 1 5


Output:
2

Circle Finding

CSES - Flight Discount Your task is to find a minimum-price flight route from Syrjälä to Metsälä. You have one discount coupon, using which you can halve the price of any single flight during the route. However, you can only use the coupon once.

Input

The first input line has two integers n and m: the number of cities and flight connections. The cities are numbered 1,2,,n. City 1 is Syrjälä, and city n is Metsälä.

After this there are m lines describing the flights. Each line has three integers a, b, and c: a flight begins at city a, ends at city b, and its price is c. Each flight is unidirectional.

You can assume that it is always possible to get from Syrjälä to Metsälä.

Output

Print one integer: the price of the cheapest route from Syrjälä to Metsälä.

When you use the discount coupon for a flight whose price is x, its price becomes x/2 (it is rounded down to an integer).

Constraints
Example

Input:
3 4
1 2 3
2 3 1
1 3 7
2 1 5


Output:
2

Round Trip II

CSES - Round Trip II Byteland has n cities and m flight connections. Your task is to design a round trip that begins in a city, goes through one or more other cities, and finally returns to the starting city. Every intermediate city on the route has to be distinct.

Input

The first input line has two integers n and m: the number of cities and flights. The cities are numbered 1,2,,n.

Then, there are m lines describing the flights. Each line has two integers a and b: there is a flight connection from city a to city b. All connections are one-way flights from a city to another city.

Output

First print an integer k: the number of cities on the route. Then print k cities in the order they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints
Example

Input:
4 5
1 3
2 1
2 4
3 2
3 4


Output:
4
2 1 3 2

Course Schedule

CSES - Course Schedule You have to complete n courses. There are m requirements of the form "course a has to be completed before course b". Your task is to find an order in which you can complete the courses.

Input

The first input line has two integers n and m: the number of courses and requirements. The courses are numbered 1,2,,n.

After this, there are m lines describing the requirements. Each line has two integers a and b: course a has to be completed before course b.

Output

Print an order in which you can complete the courses. You can print any valid order that includes all the courses.

If there are no solutions, print "IMPOSSIBLE".

Constraints
Example

Input:
5 3
1 2
3 1
4 5


Output:
3 4 1 5 2

LOngest Flight Route

CSES - Longest Flight Route Uolevi has won a contest, and the prize is a free flight trip that can consist of one or more flights through cities. Of course, Uolevi wants to choose a trip that has as many cities as possible.

Uolevi wants to fly from Syrjälä to Lehmälä so that he visits the maximum number of cities. You are given the list of possible flights, and you know that there are no directed cycles in the flight network.

Input

The first input line has two integers n and m: the number of cities and flights. The cities are numbered 1,2,,n. City 1 is Syrjälä, and city n is Lehmälä.

After this, there are m lines describing the flights. Each line has two integers a and b: there is a flight from city a to city b. Each flight is a one-way flight.

Output

First print the maximum number of cities on the route. After this, print the cities in the order they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints
Example

Input:
5 5
1 2
2 5
1 3
3 4
4 5


Output:
4
1 3 4 5

Game Routes

CSES - Game Routes A game has n levels, connected by m teleporters, and your task is to get from level 1 to level n. The game has been designed so that there are no directed cycles in the underlying graph. In how many ways can you complete the game?

Input

The first input line has two integers n and m: the number of levels and teleporters. The levels are numbered 1,2,,n.

After this, there are m lines describing the teleporters. Each line has two integers a and b: there is a teleporter from level a to level b.

Output

Print one integer: the number of ways you can complete the game. Since the result may be large, print it modulo 109+7.

Constraints
Example

Input:
4 5
1 2
2 4
1 3
3 4
1 4


Output:
3

Investigation

CSES - Investigation You are going to travel from Syrjälä to Lehmälä by plane. You would like to find answers to the following questions:
Input

The first input line contains two integers n and m: the number of cities and the number of flights. The cities are numbered 1,2,,n. City 1 is Syrjälä, and city n is Lehmälä.

After this, there are m lines describing the flights. Each line has three integers a, b, and c: there is a flight from city a to city b with price c. All flights are one-way flights.

You may assume that there is a route from Syrjälä to Lehmälä.

Output

Print four integers according to the problem statement.

Constraints
Example

Input:
4 5
1 4 5
1 2 4
2 4 5
1 3 2
3 4 3


Output:
5 2 1 2

PLanet Queries I

CSES - Planets Queries I You are playing a game consisting of n planets. Each planet has a teleporter to another planet (or the planet itself).

Your task is to process q queries of the form: when you begin on planet x and travel through k teleporters, which planet will you reach?

Input

The first input line has two integers n and q: the number of planets and queries. The planets are numbered 1,2,,n.

The second line has n integers t1,t2,,tn: for each planet, the destination of the teleporter. It is possible that ti=i.

Finally, there are q lines describing the queries. Each line has two integers x and k: you start on planet x and travel through k teleporters.

Output

Print the answer to each query.

Constraints
Example

Input:
4 3
2 1 1 4
1 2
3 4
4 1


Output:
1
2
4

Planet Queries II

CSES - Planets Queries II You are playing a game consisting of n planets. Each planet has a teleporter to another planet (or the planet itself).

You have to process q queries of the form: You are now on planet a and want to reach planet b. What is the minimum number of teleportations?

Input

The first input line contains two integers n and q: the number of planets and queries. The planets are numbered 1,2,,n.

The second line contains n integers t1,t2,,tn: for each planet, the destination of the teleporter.

Finally, there are q lines describing the queries. Each line has two integers a and b: you are now on planet a and want to reach planet b.

Output

For each query, print the minimum number of teleportations. If it is not possible to reach the destination, print 1.

Constraints
Example

Input:
5 3
2 3 2 3 2
1 2
1 3
1 4


Output:
1
2
-1

Planet Cycles

CSES - Planets Cycles You are playing a game consisting of n planets. Each planet has a teleporter to another planet (or the planet itself).

You start on a planet and then travel through teleporters until you reach a planet that you have already visited before.

Your task is to calculate for each planet the number of teleportations there would be if you started on that planet.

Input

The first input line has an integer n: the number of planets. The planets are numbered 1,2,,n.

The second line has n integers t1,t2,,tn: for each planet, the destination of the teleporter. It is possible that ti=i.

Output

Print n integers according to the problem statement.

Constraints
Example

Input:
5
2 4 3 1 4


Output:
3 3 1 3 4

Road Reparation

CSES - Road Reparation There are n cities and m roads between them. Unfortunately, the condition of the roads is so poor that they cannot be used. Your task is to repair some of the roads so that there will be a decent route between any two cities.

For each road, you know its reparation cost, and you should find a solution where the total cost is as small as possible.

Input

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,,n.

Then, there are m lines describing the roads. Each line has three integers a, b and c: there is a road between cities a and b, and its reparation cost is c. All roads are two-way roads.

Every road is between two different cities, and there is at most one road between two cities.

Output

Print one integer: the minimum total reparation cost. However, if there are no solutions, print "IMPOSSIBLE".

Constraints
Example

Input:
5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4


Output:
14

Road Construction

CSES - Road Construction There are n cities and initially no roads between them. However, every day a new road will be constructed, and there will be a total of m roads.

A component is a group of cities where there is a route between any two cities using the roads. After each day, your task is to find the number of components and the size of the largest component.

Input

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,,n.

Then, there are m lines describing the new roads. Each line has two integers a and b: a new road is constructed between cities a and b.

You may assume that every road will be constructed between two different cities.

Output

Print m lines: the required information after each day.

Constraints
Example

Input:
5 3
1 2
1 3
4 5


Output:
4 2
3 3
2 3

Flight Routes Checks

CSES - Flight Routes Check There are n cities and m flight connections. Your task is to check if you can travel from any city to any other city using the available flights.

Input

The first input line has two integers n and m: the number of cities and flights. The cities are numbered 1,2,,n.

After this, there are m lines describing the flights. Each line has two integers a and b: there is a flight from city a to city b. All flights are one-way flights.

Output

Print "YES" if all routes are possible, and "NO" otherwise. In the latter case also print two cities a and b such that you cannot travel from city a to city b.

Constraints
Example

Input:
4 5
1 2
2 3
3 1
1 4
3 4


Output:
NO
4 2

Planets and Kingdoms

CSES - Planets and Kingdoms A game has n planets, connected by m teleporters. Two planets a and b belong to the same kingdom exactly when there is a route both from a to b and from b to a. Your task is to determine for each planet its kingdom.

Input

The first input line has two integers n and m: the number of planets and teleporters. The planets are numbered 1,2,,n.

After this, there are m lines describing the teleporters. Each line has two integers a and b: you can travel from planet a to planet b through a teleporter.

Output

First print an integer k: the number of kingdoms. After this, print for each planet a kingdom label between 1 and k. You can print any valid solution.

Constraints
Example

Input:
5 6
1 2
2 3
3 1
3 4
4 5
5 4


Output:
2
1 1 1 2 2

Giant Pizza

CSES - Giant Pizza Uolevi's family is going to order a large pizza and eat it together. A total of n family members will join the order, and there are m possible toppings. The pizza may have any number of toppings.

Each family member gives two wishes concerning the toppings of the pizza. The wishes are of the form "topping x is good/bad". Your task is to choose the toppings so that at least one wish from everybody becomes true (a good topping is included in the pizza or a bad topping is not included).

Input

The first input line has two integers n and m: the number of family members and toppings. The toppings are numbered 1,2,,m.

After this, there are n lines describing the wishes. Each line has two wishes of the form "+ x" (topping x is good) or "- x" (topping x is bad).

Output

Print a line with m symbols: for each topping "+" if it is included and "-" if it is not included. You can print any valid solution.

If there are no valid solutions, print "IMPOSSIBLE".

Constraints
Example

Input:
3 5
+ 1 + 2
- 1 + 3
+ 4 - 2


Output:
- + + + -

Coin Collector

CSES - Coin Collector A game has n rooms and m tunnels between them. Each room has a certain number of coins. What is the maximum number of coins you can collect while moving through the tunnels when you can freely choose your starting and ending room?

Input

The first input line has two integers n and m: the number of rooms and tunnels. The rooms are numbered 1,2,,n.

Then, there are n integers k1,k2,,kn: the number of coins in each room.

Finally, there are m lines describing the tunnels. Each line has two integers a and b: there is a tunnel from room a to room b. Each tunnel is a one-way tunnel.

Output

Print one integer: the maximum number of coins you can collect.

Constraints
Example

Input:
4 4
4 5 2 7
1 2
2 1
1 3
2 4


Output:
16

Mail Delivery

CSES - Mail Delivery Your task is to deliver mail to the inhabitants of a city. For this reason, you want to find a route whose starting and ending point are the post office, and that goes through every street exactly once.

Input

The first input line has two integers n and m: the number of crossings and streets. The crossings are numbered 1,2,,n, and the post office is located at crossing 1.

After that, there are m lines describing the streets. Each line has two integers a and b: there is a street between crossings a and b. All streets are two-way streets.

Every street is between two different crossings, and there is at most one street between two crossings.

Output

Print all the crossings on the route in the order you will visit them. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

2n105
1m2.105
1a,bn

Example

Input:
6 8
1 2
1 3
2 3
2 4
2 6
3 5
3 6
4 5


Output:
1 2 6 3 2 4 5 3 1

De Bruijn Sequence

CSES - De Bruijn Sequence Your task is to construct a minimum-length bit string that contains all possible substrings of length n. For example, when n=2, the string 00110 is a valid solution, because its substrings of length 2 are 00, 01, 10 and 11.

Input

The only input line has an integer n.

Output

Print a minimum-length bit string that contains all substrings of length n. You can print any valid solution.

Constraints
Example

Input:
2

Output:
00110

Teleporters Path

CSES - Teleporters Path A game has n levels and m teleportes between them. You win the game if you move from level 1 to level n using every teleporter exactly once.

Can you win the game, and what is a possible way to do it?

Input

The first input line has two integers n and m: the number of levels and teleporters. The levels are numbered 1,2,,n.

Then, there are m lines describing the teleporters. Each line has two integers a and b: there is a teleporter from level a to level b.

You can assume that each pair (a,b) in the input is distinct.

Output

Print m+1 integers: the sequence in which you visit the levels during the game. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints
Example

Input:
5 6
1 2
1 3
2 4
2 5
3 1
4 2


Output:
1 3 1 2 4 2 5

Hamiltonian Flights

CSES - Hamiltonian Flights There are n cities and m flight connections between them. You want to travel from Syrjälä to Lehmälä so that you visit each city exactly once. How many possible routes are there?

Input

The first input line has two integers n and m: the number of cities and flights. The cities are numbered 1,2,,n. City 1 is Syrjälä, and city n is Lehmälä.

Then, there are m lines describing the flights. Each line has two integers a and b: there is a flight from city a to city b. All flights are one-way flights.

Output

Print one integer: the number of routes modulo 109+7.

Constraints
Example

Input:
4 6
1 2
1 3
2 3
3 2
2 4
3 4


Output:
2

Knight's Tour

CSES - Knight's Tour Given a starting position of a knight on an 8×8 chessboard, your task is to find a sequence of moves such that it visits every square exactly once.

On each move, the knight may either move two steps horizontally and one step vertically, or one step horizontally and two steps vertically.

Input

The only line has two integers x and y: the knight's starting position.

Output

Print a grid that shows how the knight moves (according to the example). You can print any valid solution.

Constraints
Example

Input:
2 1

Output:
8 1 10 13 6 3 20 17
11 14 7 2 19 16 23 4
26 9 12 15 24 5 18 21
49 58 25 28 51 22 33 30
40 27 50 59 32 29 52 35
57 48 41 44 37 34 31 62
42 39 46 55 60 63 36 53
47 56 43 38 45 54 61 64

Download Speed

CSES - Download Speed Consider a network consisting of n computers and m connections. Each connection specifies how fast a computer can send data to another computer.

Kotivalo wants to download some data from a server. What is the maximum speed he can do this, using the connections in the network?

Input

The first input line has two integers n and m: the number of computers and connections. The computers are numbered 1,2,,n. Computer 1 is the server and computer n is Kotivalo's computer.

After this, there are m lines describing the connections. Each line has three integers a, b and c: computer a can send data to computer b at speed c.

Output

Print one integer: the maximum speed Kotivalo can download data.

Constraints
Example

Input:
4 5
1 2 3
2 4 2
1 3 4
3 4 5
4 1 3


Output:
6

Police Chase

CSES - Download Speed Consider a network consisting of n computers and m connections. Each connection specifies how fast a computer can send data to another computer.

Kotivalo wants to download some data from a server. What is the maximum speed he can do this, using the connections in the network?

Input

The first input line has two integers n and m: the number of computers and connections. The computers are numbered 1,2,,n. Computer 1 is the server and computer n is Kotivalo's computer.

After this, there are m lines describing the connections. Each line has three integers a, b and c: computer a can send data to computer b at speed c.

Output

Print one integer: the maximum speed Kotivalo can download data.

Constraints
Example

Input:
4 5
1 2 3
2 4 2
1 3 4
3 4 5
4 1 3


Output:
6

School Dance

CSES - School Dance There are n boys and m girls in a school. Next week a school dance will be organized. A dance pair consists of a boy and a girl, and there are k potential pairs.

Your task is to find out the maximum number of dance pairs and show how this number can be achieved.

Input

The first input line has three integers n, m and k: the number of boys, girls, and potential pairs. The boys are numbered 1,2,,n, and the girls are numbered 1,2,,m.

After this, there are k lines describing the potential pairs. Each line has two integers a and b: boy a and girl b are willing to dance together.

Output

First print one integer r: the maximum number of dance pairs. After this, print r lines describing the pairs. You can print any valid solution.

Constraints
Example

Input:
3 2 4
1 1
1 2
2 1
3 1


Output:
2
1 2
3 1

Distinct Routes

CSES - Distinct Routes A game consists of n rooms and m teleporters. At the beginning of each day, you start in room 1 and you have to reach room n.

You can use each teleporter at most once during the game. How many days can you play if you choose your routes optimally?

Input

The first input line has two integers n and m: the number of rooms and teleporters. The rooms are numbered 1,2,,n.

After this, there are m lines describing the teleporters. Each line has two integers a and b: there is a teleporter from room a to room b.

There are no two teleporters whose starting and ending room are the same.

Output

First print an integer k: the maximum number of days you can play the game. Then, print k route descriptions according to the example. You can print any valid solution.

Constraints
Example

Input:
6 7
1 2
1 3
2 6
3 4
3 5
4 6
5 6


Output:
2
3
1 2 6
4
1 3 4 6

Static Range Sum Queries

CSES - Static Range Sum Queries Given an array of n integers, your task is to process q queries of the form: what is the sum of values in range [a,b]?

Input

The first input line has two integers n and q: the number of values and queries.

The second line has n integers x1,x2,,xn: the array values.

Finally, there are q lines describing the queries. Each line has two integers a and b: what is the sum of values in range [a,b]?

Output

Print the result of each query.

Constraints
Example

Input:
8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3


Output:
11
2
24
4

Static Range Minimum Queries

CSES - Static Range Minimum Queries Given an array of n integers, your task is to process q queries of the form: what is the minimum value in range [a,b]?

Input

The first input line has two integers n and q: the number of values and queries.

The second line has n integers x1,x2,,xn: the array values.

Finally, there are q lines describing the queries. Each line has two integers a and b: what is the minimum value in range [a,b]?

Output

Print the result of each query.

Constraints
Example

Input:
8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3


Output:
2
1
1
4

Dynamic Range Sum Queries

CSES - Dynamic Range Sum Queries Given an array of n integers, your task is to process q queries of the following types:
  1. update the value at position k to u
  2. what is the sum of values in range [a,b]?
Input

The first input line has two integers n and q: the number of values and queries.

The second line has n integers x1,x2,,xn: the array values.

Finally, there are q lines describing the queries. Each line has three integers: either "1 k u" or "2 a b".

Output

Print the result of each query of type 2.

Constraints
Example

Input:
8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 3 1
2 1 4


Output:
14
2
11

Dynamic Range Minimum Queries

CSES - Dynamic Range Minimum Queries Given an array of n integers, your task is to process q queries of the following types:
  1. update the value at position k to u
  2. what is the minimum value in range [a,b]?
Input

The first input line has two integers n and q: the number of values and queries.

The second line has n integers x1,x2,,xn: the array values.

Finally, there are q lines describing the queries. Each line has three integers: either "1 k u" or "2 a b".

Output

Print the result of each query of type 2.

Constraints
Example

Input:
8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 2 3
2 1 4


Output:
2
1
3

Range Xor Queries

CSES - Range Xor Queries Given an array of n integers, your task is to process q queries of the form: what is the xor sum of values in range [a,b]?

Input

The first input line has two integers n and q: the number of values and queries.

The second line has n integers x1,x2,,xn: the array values.

Finally, there are q lines describing the queries. Each line has two integers a and b: what is the xor sum of values in range [a,b]?

Output

Print the result of each query.

Constraints
Example

Input:
8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3


Output:
3
0
6
4

Range Update Queries

CSES - Range Update Queries Given an array of n integers, your task is to process q queries of the following types:
  1. increase each value in range [a,b] by u
  2. what is the value at position k?
Input

The first input line has two integers n and q: the number of values and queries.

The second line has n integers x1,x2,,xn: the array values.

Finally, there are q lines describing the queries. Each line has three integers: either "1 a b u" or "2 k".

Output

Print the result of each query of type 2.

Constraints
Example

Input:
8 3
3 2 4 5 1 1 5 3
2 4
1 2 5 1
2 4


Output:
5
6

Forest Queries

CSES - Forest Queries You are given an n×n grid representing the map of a forest. Each square is either empty or contains a tree. The upper-left square has coordinates (1,1), and the lower-right square has coordinates (n,n).

Your task is to process q queries of the form: how many trees are inside a given rectangle in the forest?

Input

The first input line has two integers n and q: the size of the forest and the number of queries.

Then, there are n lines describing the forest. Each line has n characters: . is an empty square and * is a tree.

Finally, there are q lines describing the queries. Each line has four integers y1, x1, y2, x2 corresponding to the corners of a rectangle.

Output

Print the number of trees inside each rectangle.

Constraints
Example

Input:
4 3
.*..
*.**
**..
****
2 2 3 4
3 1 3 1
1 1 2 2


Output:
3
1
2

Hotel Queries

CSES - Hotel Queries There are n hotels on a street. For each hotel you know the number of free rooms. Your task is to assign hotel rooms for groups of tourists. All members of a group want to stay in the same hotel.

The groups will come to you one after another, and you know for each group the number of rooms it requires. You always assign a group to the first hotel having enough rooms. After this, the number of free rooms in the hotel decreases.

Input

The first input line contains two integers n and m: the number of hotels and the number of groups. The hotels are numbered 1,2,,n.

The next line contains n integers h1,h2,,hn: the number of free rooms in each hotel.

The last line contains m integers r1,r2,,rm: the number of rooms each group requires.

Output

Print the assigned hotel for each group. If a group cannot be assigned a hotel, print 0 instead.

Constraints
Example

Input:
8 5
3 2 4 1 5 5 2 6
4 4 7 1 1


Output:
3 5 0 1 1

List Removals

CSES - List Removals You are given a list consisting of n integers. Your task is to remove elements from the list at given positions, and report the removed elements.

Input

The first input line has an integer n: the initial size of the list. During the process, the elements are numbered 1,2,,k where k is the current size of the list.

The second line has n integers x1,x2,,xn: the contents of the list.

The last line has n integers p1,p2,,pn: the positions of the elements to be removed.

Output

Print the elements in the order they are removed.

Constraints
Example

Input:
5
2 6 1 4 2
3 1 3 1 1


Output:
1 2 2 6 4

Explanation: The contents of the list are [2,6,1,4,2], [2,6,4,2], [6,4,2], [6,4], [4] and [].

Salary Queries

CSES - Salary Queries A company has n employees with certain salaries. Your task is to keep track of the salaries and process queries.

Input

The first input line contains two integers n and q: the number of employees and queries. The employees are numbered 1,2,,n.

The next line has n integers p1,p2,,pn: each employee's salary.

After this, there are q lines describing the queries. Each line has one of the following forms: Output

Print the answer to each ? query.

Constraints
Example

Input:
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3


Output:
3
2

Prefix Sum Queries

CSES - Prefix Sum Queries Given an array of n integers, your task is to process q queries of the following types:
  1. update the value at position k to u
  2. what is the maximum prefix sum in range [a,b]?
Input

The first input line has two integers n and q: the number of values and queries.

The second line has n integers x1,x2,,xn: the array values.

Finally, there are q lines describing the queries. Each line has three integers: either "1 k u" or "2 a b".

Output

Print the result of each query of type 2.

Constraints
Example

Input:
8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4


Output:
5
2
0

Pizzeria Queries

CSES - Pizzeria Queries There are n buildings on a street, numbered 1,2,,n. Each building has a pizzeria and an apartment.

The pizza price in building k is pk. If you order a pizza from building a to building b, its price (with delivery) is pa+|ab|.

Your task is to process two types of queries:
  1. The pizza price pk in building k becomes x.
  2. You are in building k and want to order a pizza. What is the minimum price?
Input

The first input line has two integers n and q: the number of buildings and queries.

The second line has n integers p1,p2,,pn: the initial pizza price in each building.

Finally, there are q lines that describe the queries. Each line is either "1 k x" or "2 k".

Output

Print the answer for each query of type 2.

Constraints
Example

Input:
6 3
8 6 4 5 7 5
2 2
1 5 1
2 2


Output:
5
4

Subarray Sum Queries

CSES - Subarray Sum Queries There is an array consisting of n integers. Some values of the array will be updated, and after each update, your task is to report the maximum subarray sum in the array.

Input

The first input line contains integers n and m: the size of the array and the number of updates. The array is indexed 1,2,,n.

The next line has n integers: x1,x2,,xn: the initial contents of the array.

Then there are m lines describing the changes. Each line has two integers k and x: the value at position k becomes x.

Output

After each update, print the maximum subarray sum. Empty subarrays (with sum 0) are allowed.

Constraints
Example

Input:
5 3
1 2 -3 5 -1
2 6
3 1
2 -2


Output:
9
13
6

Distinct Values Queries

CSES - Distinct Values Queries You are given an array of n integers and q queries of the form: how many distinct values are there in a range [a,b]?

Input

The first input line has two integers n and q: the array size and number of queries.

The next line has n integers x1,x2,,xn: the array values.

Finally, there are q lines describing the queries. Each line has two integers a and b.

Output

For each query, print the number of distinct values in the range.

Constraints
Example

Input:
5 3
3 2 3 1 2
1 3
2 4
1 5


Output:
2
3
3

Increasing Array Queries

CSES - Increasing Array Queries You are given an array that consists of n integers. The array elements are indexed 1,2,,n.

You can modify the array using the following operation: choose an array element and increase its value by one.

Your task is to process q queries of the form: when we consider a subarray from position a to position b, what is the minimum number of operations after which the subarray is increasing?

An array is increasing if each element is greater than or equal with the previous element.

Input

The first input line has two integers n and q: the size of the array and the number of queries.

The next line has n integers x1,x2,,xn: the contents of the array.

Finally, there are q lines that describe the queries. Each line has two integers a and b: the starting and ending position of a subarray.

Output

For each query, print the minimum number of operations.

Constraints
Example

Input:
5 3
2 10 4 2 5
3 5
2 2
1 4


Output:
2
0
14

Forest Queries II

CSES - Forest Queries II You are given an n×n grid representing the map of a forest. Each square is either empty or has a tree. Your task is to process q queries of the following types:
  1. Change the state (empty/tree) of a square.
  2. How many trees are inside a rectangle in the forest?
Input

The first input line has two integers n and q: the size of the forest and the number of queries.

Then, there are n lines describing the forest. Each line has n characters: . is an empty square and * is a tree.

Finally, there are q lines describing the queries. The format of each line is either "1 y x" or "2 y1 x1 y2 x2".

Output

Print the answer to each query of the second type.

Constraints
Example

Input:
4 3
.*..
*.**
**..
****
2 2 2 3 4
1 3 3
2 2 2 3 4


Output:
3
4

Range Updates and Sums

CSES - Range Updates and Sums Your task is to maintain an array of n values and efficiently process the following types of queries:
  1. Increase each value in range [a,b] by x.
  2. Set each value in range [a,b] to x.
  3. Calculate the sum of values in range [a,b].
Input

The first input line has two integers n and q: the array size and the number of queries.

The next line has n values t1,t2,,tn: the initial contents of the array.

Finally, there are q lines describing the queries. The format of each line is one of the following: "1 a b x", "2 a b x", or "3 a b".

Output

Print the answer to each sum query.

Constraints
Example

Input:
6 5
2 3 1 1 5 3
3 3 5
1 2 4 2
3 3 5
2 2 4 5
3 3 5


Output:
7
11
15

Polynomial Queries

CSES - Polynomial Queries Your task is to maintain an array of n values and efficiently process the following types of queries:
  1. Increase the first value in range [a,b] by 1, the second value by 2, the third value by 3, and so on.
  2. Calculate the sum of values in range [a,b].
Input

The first input line has two integers n and q: the size of the array and the number of queries.

The next line has n values t1,t2,,tn: the initial contents of the array.

Finally, there are q lines describing the queries. The format of each line is either "1 a b" or "2 a b".

Output

Print the answer to each sum query.

Constraints
Example

Input:
5 3
4 2 3 1 7
2 1 5
1 1 5
2 1 5


Output:
17
32

Range Queries and Copies

CSES - Range Queries and Copies Your task is to maintain a list of arrays which initially has a single array. You have to process the following types of queries:
  1. Set the value a in array k to x.
  2. Calculate the sum of values in range [a,b] in array k.
  3. Create a copy of array k and add it to the end of the list.
Input

The first input line has two integers n and q: the array size and the number of queries.

The next line has n integers t1,t2,,tn: the initial contents of the array.

Finally, there are q lines describing the queries. The format of each line is one of the following: "1 k a x", "2 k a b" or "3 k".

Output

Print the answer to each sum query.

Constraints
Example

Input:
5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5


Output:
13
13
13
15

Tree Algorithms

Subordinates

CSES - Subordinates Given the structure of a company, your task is to calculate for each employee the number of their subordinates.

Input

The first input line has an integer n: the number of employees. The employees are numbered 1,2,,n, and employee 1 is the general director of the company.

After this, there are n1 integers: for each employee 2,3,,n their direct boss in the company.

Output

Print n integers: for each employee 1,2,,n the number of their subordinates.

Constraints
Example

Input:
5
1 1 2 3


Output:
4 1 1 0 0
CSES - Tree Matching You are given a tree consisting of n nodes.

A matching is a set of edges where each node is an endpoint of at most one edge. What is the maximum number of edges in a matching?

Input

The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,,n.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Output

Print one integer: the maximum number of pairs.

Constraints
Example

Input:
5
1 2
1 3
3 4
3 5


Output:
2

Explanation: One possible matching is (1,2) and (3,4).

Tree Diameter

CSES - Tree Diameter You are given a tree consisting of n nodes.

The diameter of a tree is the maximum distance between two nodes. Your task is to determine the diameter of the tree.

Input

The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,,n.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Output

Print one integer: the diameter of the tree.

Constraints
Example

Input:
5
1 2
1 3
3 4
3 5


Output:
3

Explanation: The diameter corresponds to the path 2135.

Tree Distances I

CSES - Tree Distances I You are given a tree consisting of n nodes.

Your task is to determine for each node the maximum distance to another node.

Input

The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,,n.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Output

Print n integers: for each node 1,2,,n, the maximum distance to another node.

Constraints
Example

Input:
5
1 2
1 3
3 4
3 5


Output:
2 3 2 3 3

Tree Distances II

CSES - Tree Distances II You are given a tree consisting of n nodes.

Your task is to determine for each node the sum of the distances from the node to all other nodes.

Input

The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,,n.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Output

Print n integers: for each node 1,2,,n, the sum of the distances.

Constraints
Example

Input:
5
1 2
1 3
3 4
3 5


Output:
6 9 5 8 8

Company Queries I

CSES - Company Queries I A company has n employees, who form a tree hierarchy where each employee has a boss, except for the general director.

Your task is to process q queries of the form: who is employee x's boss k levels higher up in the hierarchy?

Input

The first input line has two integers n and q: the number of employees and queries. The employees are numbered 1,2,,n, and employee 1 is the general director.

The next line has n1 integers e2,e3,,en: for each employee 2,3,,n their boss.

Finally, there are q lines describing the queries. Each line has two integers x and k: who is employee x's boss k levels higher up?

Output

Print the answer for each query. If such a boss does not exist, print 1.

Constraints
Example

Input:
5 3
1 1 3 3
4 1
4 2
4 3


Output:
3
1
-1

Company Queries I

CSES - Company Queries I A company has n employees, who form a tree hierarchy where each employee has a boss, except for the general director.

Your task is to process q queries of the form: who is employee x's boss k levels higher up in the hierarchy?

Input

The first input line has two integers n and q: the number of employees and queries. The employees are numbered 1,2,,n, and employee 1 is the general director.

The next line has n1 integers e2,e3,,en: for each employee 2,3,,n their boss.

Finally, there are q lines describing the queries. Each line has two integers x and k: who is employee x's boss k levels higher up?

Output

Print the answer for each query. If such a boss does not exist, print 1.

Constraints
Example

Input:
5 3
1 1 3 3
4 1
4 2
4 3


Output:
3
1
-1

Company Queries II

CSES - Company Queries II A company has n employees, who form a tree hierarchy where each employee has a boss, except for the general director.

Your task is to process q queries of the form: who is the lowest common boss of employees a and b in the hierarchy?

Input

The first input line has two integers n and q: the number of employees and queries. The employees are numbered 1,2,,n, and employee 1 is the general director.

The next line has n1 integers e2,e3,,en: for each employee 2,3,,n their boss.

Finally, there are q lines describing the queries. Each line has two integers a and b: who is the lowest common boss of employees a and b?

Output

Print the answer for each query.

Constraints
Example

Input:
5 3
1 1 3 3
4 5
2 5
1 4


Output:
3
1
1

Distance Queries

CSES - Distance Queries You are given a tree consisting of n nodes.

Your task is to process q queries of the form: what is the distance between nodes a and b?

Input

The first input line contains two integers n and q: the number of nodes and queries. The nodes are numbered 1,2,,n.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Finally, there are q lines describing the queries. Each line contains two integer a and b: what is the distance between nodes a and b?

Output

Print q integers: the answer to each query.

Constraints
Example

Input:
5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4


Output:
1
3
2

Counting Paths

CSES - Counting Paths You are given a tree consisting of n nodes, and m paths in the tree.

Your task is to calculate for each node the number of paths containing that node.

Input

The first input line contains integers n and m: the number of nodes and paths. The nodes are numbered 1,2,,n.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Finally, there are m lines describing the paths. Each line contains two integers a and b: there is a path between nodes a and b.

Output

Print n integers: for each node 1,2,,n, the number of paths containing that node.

Constraints
Example

Input:
5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4


Output:
3 1 3 1 1

Subtree Queries

CSES - Subtree Queries You are given a rooted tree consisting of n nodes. The nodes are numbered 1,2,,n, and node 1 is the root. Each node has a value.

Your task is to process following types of queries:
  1. change the value of node s to x
  2. calculate the sum of values in the subtree of node s
Input

The first input line contains two integers n and q: the number of nodes and queries. The nodes are numbered 1,2,,n.

The next line has n integers v1,v2,,vn: the value of each node.

Then there are n1 lines describing the edges. Each line contans two integers a and b: there is an edge between nodes a and b.

Finally, there are q lines describing the queries. Each query is either of the form "1 s x" or "2 s".

Output

Print the answer to each query of type 2.

Constraints
Example

Input:
5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 3
1 5 3
2 3


Output:
8
10

Path Queries

CSES - Path Queries You are given a rooted tree consisting of n nodes. The nodes are numbered 1,2,,n, and node 1 is the root. Each node has a value.

Your task is to process following types of queries:
  1. change the value of node s to x
  2. calculate the sum of values on the path from the root to node s
Input

The first input line contains two integers n and q: the number of nodes and queries. The nodes are numbered 1,2,,n.

The next line has n integers v1,v2,,vn: the value of each node.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Finally, there are q lines describing the queries. Each query is either of the form "1 s x" or "2 s".

Output

Print the answer to each query of type 2.

Constraints
Example

Input:
5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 4
1 3 2
2 4


Output:
11
8

Path Queries II

CSES - Path Queries II You are given a tree consisting of n nodes. The nodes are numbered 1,2,,n. Each node has a value.

Your task is to process following types of queries:
  1. change the value of node s to x
  2. find the maximum value on the path between nodes a and b.
Input

The first input line contains two integers n and q: the number of nodes and queries. The nodes are numbered 1,2,,n.

The next line has n integers v1,v2,,vn: the value of each node.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Finally, there are q lines describing the queries. Each query is either of the form "1 s x" or "2 a b".

Output

Print the answer to each query of type 2.

Constraints
Example

Input:
5 3
2 4 1 3 3
1 2
1 3
2 4
2 5
2 3 5
1 2 2
2 3 5


Output:
4 3

Distinct Colors

CSES - Distinct Colors You are given a rooted tree consisting of n nodes. The nodes are numbered 1,2,,n, and node 1 is the root. Each node has a color.

Your task is to determine for each node the number of distinct colors in the subtree of the node.

Input

The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,,n.

The next line consists of n integers c1,c2,,cn: the color of each node.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Output

Print n integers: for each node 1,2,,n, the number of distinct colors.

Constraints
Example

Input:
5
2 3 2 2 1
1 2
1 3
3 4
3 5


Output:
3 1 2 1 1

Finding a Centroid

CSES - Finding a Centroid Given a tree of n nodes, your task is to find a centroid, i.e., a node such that when it is appointed the root of the tree, each subtree has at most n/2 nodes.

Input

The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,,n.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Output

Print one integer: a centroid node. If there are several possibilities, you can choose any of them.

Constraints
Example

Input:
5
1 2
2 3
3 4
3 5


Output:
3

Fixed-Length Paths I

CSES - Fixed-Length Paths I Given a tree of n nodes, your task is to count the number of distinct paths that consist of exactly k edges.

Input

The first input line contains two integers n and k: the number of nodes and the path length. The nodes are numbered 1,2,,n.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Output

Print one integer: the number of paths.

Constraints
Example

Input:
5 2
1 2
2 3
3 4
3 5


Output:
4

Fixed-Length Paths II

CSES - Fixed-Length Paths II Given a tree of n nodes, your task is to count the number of distinct paths that have at least k1 and at most k2 edges.

Input

The first input line contains three integers n, k1 and k2: the number of nodes and the path lengths. The nodes are numbered 1,2,,n.

Then there are n1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Output

Print one integer: the number of paths.

Constraints
Example

Input:
5 2 3
1 2
2 3
3 4
3 5


Output:
6


Mathematics



Josephus Queries

CSES - Josephus Queries Consider a game where there are n children (numbered 1,2,,n) in a circle. During the game, every second child is removed from the circle, until there are no children left.

Your task is to process q queries of the form: "when there are n children, who is the kth child that will be removed?"

Input

The first input line has an integer q: the number of queries.

After this, there are q lines that describe the queries. Each line has two integers n and k: the number of children and the position of the child.

Output

Print q integers: the answer for each query.

Constraints
Example

Input:
4
7 1
7 3
2 2
1337 1313


Output:
2
6
1
1107

Exponentiation

CSES - Exponentiation Your task is to efficiently calculate values ab modulo 109+7.

Note that in this task we assume that 00=1.

Input

The first input line contains an integer n: the number of calculations.

After this, there are n lines, each containing two integers a and b.

Output

Print each value ab modulo 109+7.

Constraints
Example

Input:
3
3 4
2 8
123 123


Output:
81
256
921450052

Exponentiation II

CSES - Exponentiation II Your task is to efficiently calculate values abc modulo 109+7.

Note that in this task we assume that 00=1.

Input

The first input line has an integer n: the number of calculations.

Afther this, there are n lines, each containing three integers a, b and c.

Output

Print each value abc modulo 109+7.

Constraints
Example

Input:
3
3 7 1
15 2 2
3 4 5


Output:
2187
50625
763327764

Counting Divisors

CSES - Counting Divisors Given n integers, your task is to report for each integer the number of its divisors.

For example, if x=18, the correct answer is 6 because its divisors are 1,2,3,6,9,18.

Input

The first input line has an integer n: the number of integers.

After this, there are n lines, each containing an integer x.

Output

For each integer, print the number of its divisors.

Constraints
Example

Input:
3
16
17
18


Output:
5
2
6

Common Divisors

CSES - Common Divisors You are given an array of n positive integers. Your task is to find two integers such that their greatest common divisor is as large as possible.

Input

The first input line has an integer n: the size of the array.

The second line has n integers x1,x2,,xn: the contents of the array.

Output

Print the maximum greatest common divisor.

Constraints
Example

Input:
5
3 14 15 7 9


Output:
7

Sum of Divisors

CSES - Sum of Divisors Let σ(n) denote the sum of divisors of an integer n. For example, σ(12)=1+2+3+4+6+12=28.

Your task is to calculate the sum i=1nσ(i) modulo 109+7.

Input

The only input line has an integer n.

Output

Print i=1nσ(i) modulo 109+7.

Constraints
Example

Input:
5

Output:
21

Divisor Analysis

CSES - Divisor Analysis Given an integer, your task is to find the number, sum and product of its divisors. As an example, let us consider the number 12: Since the input number may be large, it is given as a prime factorization.

Input

The first line has an integer n: the number of parts in the prime factorization.

After this, there are n lines that describe the factorization. Each line has two numbers x and k where x is a prime and k is its power.

Output

Print three integers modulo 109+7: the number, sum and product of the divisors.

Constraints
Example

Input:
2
2 2
3 1


Output:
6 28 1728

Prime Multiples

CSES - Prime Multiples You are given k distinct prime numbers a1,a2,,ak and an integer n.

Your task is to calculate how many of the first n positive integers are divisible by at least one of the given prime numbers.

Input

The first input line has two integers n and k.

The second line has k prime numbers a1,a2,,ak.

Output

Print one integer: the number integers within the interval 1,2,,n that are divisible by at least one of the prime numbers.

Constraints
Example

Input:
20 2
2 5


Output:
12

Explanation: the 12 numbers are 2,4,5,6,8,10,12,14,15,16,18,20.

Counting Coprime Pairs

CSES - Counting Coprime Pairs Given a list of n positive integers, your task is to count the number of pairs of integers that are coprime (i.e., their greatest common divisor is one).

Input

The first input line has an integer n: the number of elements.

The next line has n integers x1,x2,,xn: the contents of the list.

Output

Print one integer: the answer for the task.

Constraints
Example

Input:
8
5 4 20 1 16 17 5 15


Output:
19

Binomial Coefficients

CSES - Binomial Coefficients Your task is to calculate n binomial coefficients modulo 109+7.

A binomial coefficient (ab) can be calculated using the formula a!b!(ab)!. We assume that a and b are integers and 0ba.

Input

The first input line contains an integer n: the number of calculations.

After this, there are n lines, each of which contains two integers a and b.

Output

Print each binomial coefficient modulo 109+7.

Constraints
Example

Input:
3
5 3
8 1
9 5


Output:
10
8
126

Creating Strings II

CSES - Creating Strings II Given a string, your task is to calculate the number of different strings that can be created using its characters.

Input

The only input line has a string of length n. Each character is between a–z.

Output

Print the number of different strings modulo 109+7.

Constraints
Example

Input:
aabac

Output:
20

Distributing Apples

CSES - Distributing Apples There are n children and m apples that will be distributed to them. Your task is to count the number of ways this can be done.

For example, if n=3 and m=2, there are 6 ways: [0,0,2], [0,1,1], [0,2,0], [1,0,1], [1,1,0] and [2,0,0].

Input

The only input line has two integers n and m.

Output

Print the number of ways modulo 109+7.

Constraints
Example

Input:
3 2

Output:
6

Christmas Party

CSES - Christmas Party There are n children at a Christmas party, and each of them has brought a gift. The idea is that everybody will get a gift brought by someone else.

In how many ways can the gifts be distributed?

Input

The only input line has an integer n: the number of children.

Output

Print the number of ways modulo 109+7.

Constraints
Example

Input:
4

Output:
9

Bracket Sequences I

CSES - Bracket Sequences I Your task is to calculate the number of valid bracket sequences of length n. For example, when n=6, there are 5 sequences: Input

The only input line has an integer n.

Output

Print the number of sequences modulo 109+7.

Constraints
Example

Input:
6

Output:
5

Bracket Sequences II

CSES - Bracket Sequences II Your task is to calculate the number of valid bracket sequences of length n when a prefix of the sequence is given.

Input

The first input line has an integer n.

The second line has a string of k characters: the prefix of the sequence.

Output

Print the number of sequences modulo 109+7.

Constraints
Example

Input:
6
(()


Output:
2

Explanation: There are two possible sequences: (())() and (()()).

Counting Necklaces

CSES - Counting Necklaces Your task is to count the number of different necklaces that consist of n pearls and each pearl has m possible colors.

Two necklaces are considered to be different if it is not possible to rotate one of them so that they look the same.

Input

The only input line has two numbers n and m: the number of pearls and colors.

Output

Print one integer: the number of different necklaces modulo 109+7.

Constraints
Example

Input:
4 3

Output:
24

Counting Grids

CSES - Counting Grids Your task is to count the number of different n×n grids whose each square is black or white.

Two grids are considered to be different if it is not possible to rotate one of them so that they look the same.

Input

The only input line has an integer n: the size of the grid.

Output

Print one integer: the number of grids modulo 109+7.

Constraints
Example

Input:
4

Output:
16456

Fibonacci Numbers

CSES - Fibonacci Numbers The Fibonacci numbers can be defined as follows: Your task is to calculate the value of Fn for a given n.

Input

The only input line has an integer n.

Output

Print the value of Fn modulo 109+7.

Constraints
Example

Input:
10

Output:
55

Throwing Dice

CSES - Throwing Dice Your task is to calculate the number of ways to get a sum n by throwing dice. Each throw yields an integer between 16.

For example, if n=10, some possible ways are 3+3+4, 1+4+1+4 and 1+1+6+1+1.

Input

The only input line contains an integer n.

Output

Print the number of ways modulo 109+7.

Constraints
Example

Input:
8

Output:
125

Graph Paths I

CSES - Graph Paths I Consider a directed graph that has n nodes and m edges. Your task is to count the number of paths from node 1 to node n with exactly k edges.

Input

The first input line contains three integers n, m and k: the number of nodes and edges, and the length of the path. The nodes are numbered 1,2,,n.

Then, there are m lines describing the edges. Each line contains two integers a and b: there is an edge from node a to node b.

Output

Print the number of paths modulo 109+7.

Constraints
Example

Input:
3 4 8
1 2
2 3
3 1
3 2


Output:
2

Explanation: The paths are 123123123 and 123232323.

Graph Paths II

CSES - Graph Paths II Consider a directed weighted graph having n nodes and m edges. Your task is to calculate the minimum path length from node 1 to node n with exactly k edges.

Input

The first input line contains three integers n, m and k: the number of nodes and edges, and the length of the path. The nodes are numbered 1,2,,n.

Then, there are m lines describing the edges. Each line contains three integers a, b and c: there is an edge from node a to node b with weight c.

Output

Print the minimum path length. If there are no such paths, print 1.

Constraints
Example

Input:
3 4 8
1 2 5
2 3 4
3 1 1
3 2 2


Output:
27

Graph Paths II

CSES - Graph Paths II Consider a directed weighted graph having n nodes and m edges. Your task is to calculate the minimum path length from node 1 to node n with exactly k edges.

Input

The first input line contains three integers n, m and k: the number of nodes and edges, and the length of the path. The nodes are numbered 1,2,,n.

Then, there are m lines describing the edges. Each line contains three integers a, b and c: there is an edge from node a to node b with weight c.

Output

Print the minimum path length. If there are no such paths, print 1.

Constraints
Example

Input:
3 4 8
1 2 5
2 3 4
3 1 1
3 2 2


Output:
27

Dice Probability

CSES - Dice Probability You throw a dice n times, and every throw produces an outcome between 1 and 6. What is the probability that the sum of outcomes is between a and b?

Input

The only input line contains three integers n, a and b.

Output

Print the probability rounded to six decimal places.

Constraints
Example

Input:
2 9 10

Output:
0.194444

Moving Robots

CSES - Moving Robots Each square of an 8×8 chessboard has a robot. Each robot independently moves k steps, and there can be many robots on the same square.

On each turn, a robot moves one step left, right, up or down, but not outside the board. It randomly chooses a direction among those where it can move.

Your task is to calculate the expected number of empty squares after k turns.

Input

The only input line has an integer k.

Output

Print the expected number of empty squares rounded to six decimal places.

Constraints
Example

Input:
10

Output:
23.120740

Candy Lottery

CSES - Candy Lottery There are n children, and each of them independently gets a random integer number of candies between 1 and k.

What is the expected maximum number of candies a child gets?

Input

The only input line contains two integers n and k.

Output

Print the expected number rounded to six decimal places.

Constraints
Example

Input:
2 3

Output:
2.444444

Inversion Probability

CSES - Inversion Probability An array has n integers x1,x2,,xn, and each of them has been randomly chosen between 1 and ri. An inversion is a pair (a,b) where a<b and xa>xb.

What is the expected number of inversions in the array?

Input

The first input line contains an integer n: the size of the array.

The second line contains n integers r1,r2,,rn: the range of possible values for each array position.

Output

Print the expected number of inversions rounded to six decimal places.

Constraints
Example

Input:
3
5 2 7


Output:
1.057143

Stick Game

CSES - Stick Game Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game.

A set P={p1,p2,,pk} determines the allowed moves. For example, if P={1,3,4}, a player may remove 1, 3 or 4 sticks.

Your task is find out for each number of sticks 1,2,,n if the first player has a winning or losing position.

Input

The first input line has two integers n and k: the number of sticks and moves.

The next line has k integers p1,p2,,pk that describe the allowed moves. All integers are distinct, and one of them is 1.

Output

Print a string containing n characters: W means a winning position, and L means a losing position.

Constraints
Example

Input:
10 3
1 3 4


Output:
WLWWWWLWLW

Nim Game I

CSES - Nim Game I There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes any number of sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

Input

The first input line contains an integer t: the number of tests. After this, t test cases are described:

The first line contains an integer n: the number of heaps.

The next line has n integers x1,x2,,xn: the number of sticks in each heap.

Output

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

Constraints
Example

Input:
3
4
5 7 2 5
2
4 1
3
3 5 6


Output:
first
first
second

Nim Game II

CSES - Nim Game II There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes 1, 2, or 3 sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

Input

The first input line contains an integer t: the number of tests. After this, t test cases are described:

The first line contains an integer n: the number of heaps.

The next line has n integers x1,x2,,xn: the number of sticks in each heap.

Output

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

Constraints
Example

Input:
3
4
5 7 2 5
2
4 1
3
4 4 4


Output:
first
first
second

Stair Game

CSES - Stair Game There is a staircase consisting of n stairs, numbered 1,2,,n. Initially, each stair has some number of balls.

There are two players who move alternately. On each move, a player chooses a stair k where k1 and it has at least one ball. Then, the player moves any number of balls from stair k to stair k1. The player who moves last wins the game.

Your task is to find out who wins the game when both players play optimally.

Note that if there are no possible moves at all, the second player wins.

Input

The first input line has an integer t: the number of tests. After this, t test cases are described:

The first line contains an integer n: the number of stairs.

The next line has n integers p1,p2,,pn: the initial number of balls on each stair.

Output

For each test, print "first" if the first player wins the game and "second" if the second player wins the game.

Constraints
Example

Input:
3
3
0 2 1
4
1 1 1 1
2
5 3


Output:
first
second
first

Grundy's Game

CSES - Grundy's Game There is a heap of n coins and two players who move alternately. On each move, a player chooses a heap and divides into two nonempty heaps that have a different number of coins. The player who makes the last move wins the game.

Your task is to find out who wins if both players play optimally.

Input

The first input line contains an integer t: the number of tests.

After this, there are t lines that describe the tests. Each line has an integer n: the number of coins in the initial heap.

Output

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

Constraints
Example

Input:
3
6
7
8


Output:
first
second
first

Another Game

CSES - Another Game There are n heaps of coins and two players who move alternately. On each move, a player selects some of the nonempty heaps and removes one coin from each heap. The player who removes the last coin wins the game.

Your task is to find out who wins if both players play optimally.

Input

The first input line contains an integer t: the number of tests. After this, t test cases are described:

The first line contains an integer n: the number of heaps.

The next line has n integers x1,x2,,xn: the number of coins in each heap.

Output

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

Constraints
Example

Input:
3
3
1 2 3
2
2 2
4
5 5 4 5


Output:
first
second
first

Word Combinations

CSES - Word Combinations You are given a string of length n and a dictionary containing k words. In how many ways can you create the string using the words?

Input

The first input line has a string containing n characters between a–z.

The second line has an integer k: the number of words in the dictionary.

Finally there are k lines describing the words. Each word is unique and consists of characters a–z.

Output

Print the number of ways modulo 109+7.

Constraints
Example

Input:
ababc
4
ab
abab
c
cb


Output:
2

Explanation: The possible ways are ab+ab+c and abab+c.

String Matching

CSES - String Matching Given a string and a pattern, your task is to count the number of positions where the pattern occurs in the string.

Input

The first input line has a string of length n, and the second input line has a pattern of length m. Both of them consist of characters a–z.

Output

Print one integer: the number of occurrences.

Constraints
Example

Input:
saippuakauppias
pp


Output:
2

Finding Borders

CSES - Finding Borders A border of a string is a prefix that is also a suffix of the string but not the whole string. For example, the borders of abcababcab are ab and abcab.

Your task is to find all border lengths of a given string.

Input

The only input line has a string of length n consisting of characters a–z.

Output

Print all border lengths of the string in increasing order.

Constraints
Example

Input:
abcababcab

Output:
2 5

Finding Periods

CSES - Finding Periods A period of a string is a prefix that can be used to generate the whole string by repeating the prefix. The last repetition may be partial. For example, the periods of abcabca are abc, abcabc and abcabca.

Your task is to find all period lengths of a string.

Input

The only input line has a string of length n consisting of characters a–z.

Output

Print all period lengths in increasing order.

Constraints
Example

Input:
abcabca

Output:
3 6 7

Minimal Rotation

CSES - Minimal Rotation A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of acab are acab, caba, abac, and baca.

Your task is to determine the lexicographically minimal rotation of a string.

Input

The only input line contains a string of length n. Each character is one of a–z.

Output

Print the lexicographically minimal rotation.

Constraints
Example

Input:
acab

Output:
abac

Longest Palindrome

CSES - Longest Palindrome Given a string, your task is to determine the longest palindromic substring of the string. For example, the longest palindrome in aybabtu is bab.

Input

The only input line contains a string of length n. Each character is one of a–z.

Output

Print the longest palindrome in the string. If there are several solutions, you may print any of them.

Constraints
Example

Input:
aybabtu

Output:
bab

Required Substring

CSES - Required Substring Your task is to calculate the number of strings of length n having a given pattern of length m as their substring. All strings consist of characters A–Z.

Input

The first input line has an integer n: the length of the final string.

The second line has a pattern of length m.

Output

Print the number of strings modulo 109+7.

Constraints
Example

Input:
6
ABCDB


Output:
52

Explanation: The final string will be of the form ABCDBx or xABCDB where x is any character between A–Z.

Palindrome Queries

CSES - Palindrome Queries You are given a string that consists of n characters between a–z. The positions of the string are indexed 1,2,,n.

Your task is to process m operations of the following types:
  1. Change the character at position k to x
  2. Check if the substring from position a to position b is a palindrome
Input

The first input line has two integers n and m: the length of the string and the number of operations.

The next line has a string that consists of n characters.

Finally, there are m lines that describe the operations. Each line is of the form "1 k x" or "2 a b".

Output

For each operation 2, print YES if the substring is a palindrome and NO otherwise.

Constraints
Example

Input:
7 5
aybabtu
2 3 5
1 3 x
2 3 5
1 5 x
2 3 5


Output:
YES
NO
YES

Finding Patterns

CSES - Finding Patterns Given a string and patterns, check for each pattern if it appears in the string.

Input

The first input line has a string of length n.

The next input line has an integer k: the number of patterns. Finally, there are k lines that describe the patterns.

The string and the patterns consist of characters a–z.

Output

For each pattern, print "YES" if it appears in the string and "NO" otherwise.

Constraints
Example

Input:
aybabtu
3
bab
abc
ayba


Output:
YES
NO
YES

Counting Patterns

CSES - Counting Patterns Given a string and patterns, count for each pattern the number of positions where it appears in the string.

Input

The first input line has a string of length n.

The next input line has an integer k: the number of patterns. Finally, there are k lines that describe the patterns.

The string and the patterns consist of characters a–z.

Output

For each pattern, print the number of positions.

Constraints
Example

Input:
aybabtu
3
bab
abc
a


Output:
1
0
2

Pattern Positions

CSES - Pattern Positions Given a string and patterns, find for each pattern the first position (1-indexed) where it appears in the string.

Input

The first input line has a string of length n.

The next input line has an integer k: the number of patterns. Finally, there are k lines that describe the patterns.

The string and the patterns consist of characters a–z.

Output

Print the first position for each pattern (or 1 if it does not appear at all).

Constraints
Example

Input:
aybabtu
3
bab
abc
a


Output:
3
-1
1

Distinct Substrings

CSES - Distinct Substrings Count the number of distinct substrings that appear in a string.

Input

The only input line has a string of length n that consists of characters a–z.

Output

Print one integer: the number of substrings.

Constraints
Example

Input:
abaa

Output:
8

Explanation: the substrings are a, b, aa, ab, ba, aba, baa and abaa.

Repeating Substring

CSES - Repeating Substring A repeating substring is a substring that occurs in two (or more) locations in the string. Your task is to find the longest repeating substring in a given string.

Input

The only input line has a string of length n that consists of characters a–z.

Output

Print the longest repeating substring. If there are several possibilities, you can print any of them. If there is no repeating substring, print 1.

Constraints
Example

Input:
cabababc

Output:
abab

String Functions

CSES - String Functions We consider a string of n characters, indexed 1,2,,n. Your task is to calculate all values of the following functions:
Note that the function z is used in the Z-algorithm, and the function π is used in the KMP algorithm.

Input

The only input line has a string of length n. Each character is between a–z.

Output

Print two lines: first the values of the z function, and then the values of the π function.

Constraints
Example

Input:
abaabca

Output:
0 0 1 2 0 0 1
0 0 1 1 2 0 1

Substring Order I

CSES - Substring Order I You are given a string of length n. If all of its distinct substrings are ordered lexicographically, what is the kth smallest of them?

Input

The first input line has a string of length n that consists of characters a–z.

The second input line has an integer k.

Output

Print the kth smallest distinct substring in lexicographical order.

Constraints
Example

Input:
babaacbaab
10


Output:
aba

Explanation: The 10 smallest distinct substrings in order are a, aa, aab, aac, aacb, aacba, aacbaa, aacbaab, ab, and aba.

Substring Order II

CSES - Substring Order II You are given a string of length n. If all of its substrings (not necessarily distinct) are ordered lexicographically, what is the kth smallest of them?

Input

The first input line has a string of length n that consists of characters a–z.

The second input line has an integer k.

Output

Print the kth smallest substring in lexicographical order.

Constraints
Example

Input:
baabaa
10


Output:
ab

Explanation: The 10 smallest substrings in order are a, a, a, a, aa, aa, aab, aaba, aabaa, and ab.

Substring Distribution

CSES - Substring Distribution You are given a string of length n. For every integer between 1n you need to print the number of distinct substrings of that length.

Input

The only input line has a string of length n that consists of characters a–z.

Output

For each integer between 1n print the number of distinct substrings of that length.

Constraints
Example

Input:
abab

Output:
2 2 2 1


Geometry



Point Location Test

CSES - Point Location Test There is a line that goes through the points p1=(x1,y1) and p2=(x2,y2). There is also a point p3=(x3,y3).

Your task is to determine whether p3 is located on the left or right side of the line or if it touches the line when we are looking from p1 to p2.

Input

The first input line has an integer t: the number of tests.

After this, there are t lines that describe the tests. Each line has six integers: x1, y1, x2, y2, x3 and y3.

Output

For each test, print "LEFT", "RIGHT" or "TOUCH".

Constraints
Example

Input:
3
1 1 5 3 2 3
1 1 5 3 4 1
1 1 5 3 3 2


Output:
LEFT
RIGHT
TOUCH

Line Segment Intersection

CSES - Line Segment Intersection There are two line segments: the first goes through the points (x1,y1) and (x2,y2), and the second goes through the points (x3,y3) and (x4,y4).

Your task is to determine if the line segments intersect, i.e., they have at least one common point.

Input

The first input line has an integer t: the number of tests.

After this, there are t lines that describe the tests. Each line has eight integers x1, y1, x2, y2, x3, y3, x4 and y4.

Output

For each test, print "YES" if the line segments intersect and "NO" otherwise.

Constraints
Example

Input:
5
1 1 5 3 1 2 4 3
1 1 5 3 1 1 4 3
1 1 5 3 2 3 4 1
1 1 5 3 2 4 4 1
1 1 5 3 3 2 7 4


Output:
NO
YES
YES
YES
YES

Polygon Area

CSES - Polygon Area Your task is to calculate the area of a given polygon.

The polygon consists of n vertices (x1,y1),(x2,y2),,(xn,yn). The vertices (xi,yi) and (xi+1,yi+1) are adjacent for i=1,2,,n1, and the vertices (x1,y1) and (xn,yn) are also adjacent.

Input

The first input line has an integer n: the number of vertices.

After this, there are n lines that describe the vertices. The ith such line has two integers xi and yi.

You may assume that the polygon is simple, i.e., it does not intersect itself.

Output

Print one integer: 2a where the area of the polygon is a (this ensures that the result is an integer).

Constraints
Example

Input:
4
1 1
4 2
3 5
1 4


Output:
16

Point in Polygon

CSES - Point in Polygon You are given a polygon of n vertices and a list of m points. Your task is to determine for each point if it is inside, outside or on the boundary of the polygon.

The polygon consists of n vertices (x1,y1),(x2,y2),,(xn,yn). The vertices (xi,yi) and (xi+1,yi+1) are adjacent for i=1,2,,n1, and the vertices (x1,y1) and (xn,yn) are also adjacent.

Input

The first input line has two integers n and m: the number of vertices in the polygon and the number of points.

After this, there are n lines that describe the polygon. The ith such line has two integers xi and yi.

You may assume that the polygon is simple, i.e., it does not intersect itself.

Finally, there are m lines that describe the points. Each line has two integers x and y.

Output

For each point, print "INSIDE", "OUTSIDE" or "BOUNDARY".

Constraints
Example

Input:
4 3
1 1
4 2
3 5
1 4
2 3
3 1
1 3


Output:
INSIDE
OUTSIDE
BOUNDARY

Polygon Lattice Points

CSES - Polygon Lattice Points Given a polygon, your task is to calculate the number of lattice points inside the polygon and on its boundary. A lattice point is a point whose coordinates are integers.

The polygon consists of n vertices (x1,y1),(x2,y2),,(xn,yn). The vertices (xi,yi) and (xi+1,yi+1) are adjacent for i=1,2,,n1, and the vertices (x1,y1) and (xn,yn) are also adjacent.

Input

The first input line has an integer n: the number of vertices.

After this, there are n lines that describe the vertices. The ith such line has two integers xi and yi.

You may assume that the polygon is simple, i.e., it does not intersect itself.

Output

Print two integers: the number of lattice points inside the polygon and on its boundary.

Constraints
Example

Input:
4
1 1
5 3
3 5
1 4


Output:
6 8

Minimum Euclidean Distance

CSES - Minimum Euclidean Distance Given a set of points in the two-dimensional plane, your task is to find the minimum Euclidean distance between two distinct points.

The Euclidean distance of points (x1,y1) and (x2,y2) is (x1x2)2+(y1y2)2.

Input

The first input line has an integer n: the number of points.

After this, there are n lines that describe the points. Each line has two integers x and y. You may assume that each point is distinct.

Output

Print one integer: d2 where d is the minimum Euclidean distance (this ensures that the result is an integer).

Constraints
Example

Input:
4
2 1
4 4
1 2
6 3


Output:
2

Convex Hull

CSES - Convex Hull Given a set of n points in the two-dimensional plane, your task is to determine the convex hull of the points.

Input

The first input line has an integer n: the number of points.

After this, there are n lines that describe the points. Each line has two integers x and y: the coordinates of a point.

You may assume that each point is distinct, and the area of the hull is positive.

Output

First print an integer k: the number of points in the convex hull.

After this, print k lines that describe the points. You can print the points in any order. Print all points that lie on the convex hull.

Constraints
Example

Input:
6
2 1
2 5
3 3
4 3
4 4
6 3


Output:
4
2 1
2 5
4 4
6 3

Additional Problems

Shortest Subsequence

CSES - Shortest Subsequence You are given a DNA sequence consisting of characters A, C, G, and T.

Your task is to find the shortest DNA sequence that is not a subsequence of the original sequence.

Input

The only input line contains a DNA sequence with n characters.

Output

Print the shortest DNA sequence that is not a subsequence of the original sequence. If there are several solutions, you may print any of them.

Constraints
Example

Input:
ACGTACGT

Output:
AAA

Counting Bits

CSES - Counting Bits Your task is to count the number of one bits in the binary representations of integers between 1 and n.

Input

The only input line has an integer n.

Output

Print the number of one bits in the binary representations of integers between 1 and n.

Constraints
Example

Input:
7

Output:
12

Explanation: The binary representations of 17 are 1, 10, 11, 100, 101, 110, and 111, so there are a total of 12 one bits.

Swap Game

CSES - Swap Game You are given a 3×3 grid containing the numbers 1,2,,9. Your task is to perform a sequence of moves so that the grid will look like this:

1 2 3
4 5 6
7 8 9


On each move, you can swap the numbers in any two adjacent squares (horizontally or vertically). What is the minimum number of moves required?

Input

The input has three lines, and each of them has three integers.

Output

Print one integer: the minimum number of moves.

Example

Input:
2 1 3
7 5 9
8 4 6


Output:
4

Prüfer Code

CSES - Prüfer Code A Prüfer code of a tree of n nodes is a sequence of n2 integers that uniquely specifies the structure of the tree.

The code is constructed as follows: As long as there are at least three nodes left, find a leaf with the smallest label, add the label of its only neighbor to the code, and remove the leaf from the tree.

Given a Prüfer code of a tree, your task is to construct the original tree.

Input

The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,,n.

The second line contains n2 integers: the Prüfer code.

Output

Print n1 lines describing the edges of the tree. Each line has to contain two integers a and b: there is an edge between nodes a and b. You can print the edges in any order.

Constraints
Example

Input:
5
2 2 4


Output:
1 2
2 3
2 4
4 5

Acyclic Graph Edges

CSES - Acyclic Graph Edges Given an undirected graph, your task is to choose a direction for each edge so that the resulting directed graph is acyclic.

Input

The first input line has two integers n and m: the number of nodes and edges. The nodes are numbered 1,2,,n.

After this, there are m lines describing the edges. Each line has two distinct integers a and b: there is an edge between nodes a and b.

Output

Print m lines describing the directions of the edges. Each line has two integers a and b: there is an edge from node a to node b. You can print any valid solution.

Constraints
Example

Input:
3 3
1 2
2 3
3 1


Output:
1 2
3 2
3 1

Strongly Connected Edges

CSES - Strongly Connected Edges Given an undirected graph, your task is to choose a direction for each edge so that the resulting directed graph is strongly connected.

Input

The first input line has two integers n and m: the number of nodes and edges. The nodes are numbered 1,2,,n.

After this, there are m lines describing the edges. Each line has two integers a and b: there is an edge between nodes a and b.

You may assume that the graph is simple, i.e., there are at most one edge between two nodes and every edge connects two distinct nodes.

Output

Print m lines describing the directions of the edges. Each line has two integers a and b: there is an edge from node a to node b. You can print any valid solution.

If there are no solutions, only print "IMPOSSIBLE".

Constraints
Example

Input:
3 3
1 2
1 3
2 3


Output:
1 2
2 3
3 1

Even Outdegree Edges

CSES - Even Outdegree Edges Given an undirected graph, your task is to choose a direction for each edge so that in the resulting directed graph each node has an even outdegree. The outdegree of a node is the number of edges coming out of that node.

Input

The first input line has two integers n and m: the number of nodes and edges. The nodes are numbered 1,2,,n.

After this, there are m lines describing the edges. Each line has two integers a and b: there is an edge between nodes a and b.

You may assume that the graph is simple, i.e., there is at most one edge between any two nodes and every edge connects two distinct nodes.

Output

Print m lines describing the directions of the edges. Each line has two integers a and b: there is an edge from node a to node b. You can print any valid solution.

If there are no solutions, only print "IMPOSSIBLE".

Constraints
Example

Input:
4 4
1 2
2 3
3 4
1 4


Output:
1 2
3 2
3 4
1 4

Multiplication Table

CSES - Multiplication Table Find the middle element when the numbers in an n×n multiplication table are sorted in increasing order. It is assumed that n is odd.

For example, the 3×3 multiplication table is as follows:
123246369

The numbers in increasing order are [1,2,2,3,3,4,6,6,9], so the answer is 3.

Input

The only input line has an integer n.

Output

Print one integer: the answer to the task.

Constraints
Example

Input:
3

Output:
3

Advertisement

CSES - Advertisement A fence consists of n vertical boards. The width of each board is 1 and their heights may vary.

You want to attach a rectangular advertisement to the fence. What is the maximum area of such an advertisement?

Input

The first input line contains an integer n: the width of the fence.

After this, there are n integers k1,k2,,kn: the height of each board.

Output

Print one integer: the maximum area of an advertisement.

Constraints
Example

Input:
8
4 1 5 3 3 2 4 1


Output:
10

Special Substrings

CSES - Special Substrings A substring is called special if every character that appears in the string appears the same number of times in the substring.

Your task is to count the number of special substrings in a given string.

Input

The only input line has a string of length n. Every character is between a...z.

Output

Print one integer: the number of special substrings.

Constraints
Example

Input:
abccabab

Output:
5

Explanation: The special substrings are abc, cab, abccab, bccaba and ccabab.

Permutation Inversions

CSES - Permutation Inversions Your task is to count the number of permutations of 1,2,,n that have exactly k inversions (i.e., pairs of elements in the wrong order).

For example, when n=4 and k=3, there are 6 such permutations: Input

The only input line has two integers n and k.

Output

Print the answer modulo 109+7.

Constraints
Example

Input:
4 3

Output:
6

Maximum Xor Subarray

CSES - Maximum Xor Subarray Given an array of n integers, your task is to find the maximum xor sum in a subarray.

Input

The first input line has an integer n: the size of the array.

The next line has n integers x1,x2,,xn: the contents of the array.

Output

Print one integer: the maximum xor sum in a subarray.

Constraints
Example

Input:
4
5 1 5 9


Output:
13

Movie Festival Queries

CSES - Movie Festival Queries In a movie festival, n movies will be shown. You know the starting and ending time of each movie.

Your task is to process q queries of the form: if you arrive and leave the festival at specific times, what is the maximum number of movies you can watch?

You can watch two movies if the first movie ends before or exactly when the second movie starts. You can start the first movie exactly when you arrive and leave exactly when the last movie ends.

Input

The first input line has two integers n and q: the number of movies and queries.

After this, there are n lines describing the movies. Each line has two integers a and b: the starting and ending time of a movie.

Finally, there are q lines describing the queries. Each line has two integers a and b: your arrival and leaving time.

Output

Print the maximum number of movies for each query.

Constraints
Example

Input:
4 3
2 5
6 10
4 7
9 10
5 9
2 10
7 10


Output:
0
2
1

Chess Tournament

CSES - Chess Tournament There will be a chess tournament of n players. Each player has announced the number of games they want to play.

Each pair of players can play at most one game. Your task is to determine which games will be played so that everybody will be happy.

Input

The first input line has an integer n: the number of players. The players are numbered 1,2,,n.

The next line has n integers x1,x2,,xn: for each player, the number of games they want to play.

Output

First print an integer k: the number of games. Then, print k lines describing the games. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints
Example

Input:
5
1 3 2 0 2


Output:
4
1 2
2 3
2 5
3 5

Tree Traversals

CSES - Tree Traversals There are three common ways to traverse the nodes of a binary tree:
There is a binary tree of n nodes with distinct labels. You are given the preorder and inorder traversals of the tree, and your task is to determine its postorder traversal.

Input

The first input line has an integer n: the number of nodes. The nodes are numbered 1,2,,n.

After this, there are two lines describing the preorder and inorder traversals of the tree. Both lines consist of n integers.

You can assume that the input corresponds to a binary tree.

Output

Print the postorder traversal of the tree.

Constraints
Example

Input:
5
5 3 2 1 4
3 5 1 2 4


Output:
3 1 4 2 5

Network Renovation

CSES - Network Renovation Syrjälä's network consists of n computers and n1 connections between them. It is possible to send data between any two computers.

However, if any connection breaks down, it will no longer be possible to send data between some computers. Your task is to add the minimum number of new connections in such a way that you can still send data between any two computers even if any single connection breaks down.

Input

The first input line has an integer n: the number of computers. The computers are numbered 1,2,,n.

After this, there are n1 lines describing the connections. Each line has two integers a and b: there is a connection between computers a and b.

Output

First print an integer k: the minimum number of new connections. After this, print k lines describing the connections. You can print any valid solution.

Constraints
Example

Input:
5
1 2
1 3
3 4
3 5


Output:
2
2 4
4 5

Graph Girth

CSES - Graph Girth Given an undirected graph, your task is to determine its girth, i.e., the length of its shortest cycle.

Input

The first input line has two integers n and m: the number of nodes and edges. The nodes are numbered 1,2,,n.

After this, there are m lines describing the edges. Each line has two integers a and b: there is an edge between nodes a and b.

You may assume that there is at most one edge between each two nodes.

Output

Print one integer: the girth of the graph. If there are no cycles, print 1.

Constraints
Example

Input:
5 6
1 2
1 3
2 4
2 5
3 4
4 5


Output:
3

Intersection Points

CSES - Intersection Points Given n horizontal and vertical line segments, your task is to calculate the number of their intersection points.

You can assume that no parallel line segments intersect, and no endpoint of a line segment is an intersection point.

Input

The first input line has an integer n: the number of line segments.

Then there are n lines describing the line segments. Each line has four integers: x1, y1, x2 and y2: a line segment begins at point (x1,y1) and ends at point (x2,y2).

Output

Print the number of intersection points.

Constraints
Example

Input:
3
2 3 7 3
3 1 3 5
6 2 6 6


Output:
2

Inverse Inversions

CSES - Inverse Inversions Your task is to create a permutation of numbers 1,2,,n that has exactly k inversions.

An inversion is a pair (a,b) where a<b and pa>pb where pi denotes the number at position i in the permutation.

Input

The only input line has two integers n and k.

Output

Print a line that contains the permutation. You can print any valid solution.

Constraints
Example

Input:
5 4

Output:
1 5 2 4 3

Monotone Subsequences

CSES - Monotone Subsequences Your task is to create a permutation of numbers 1,2,,n whose longest monotone subsequence has exactly k elements.

A monotone subsequence is either increasing or decreasing. For example, some monotone subsequences in [2,1,4,5,3] are [2,4,5] and [4,3].

Input

The first input line has an integer t: the number of tests.

After this, there are t lines. Each line has two integers n and k.

Output

For each test, print a line that contains the permutation. You can print any valid solution. If there are no solutions, print "IMPOSSIBLE".

Constraints
Example

Input:
3
5 3
5 2
7 7


Output:
2 1 4 5 3
IMPOSSIBLE
1 2 3 4 5 6 7

String Reorder

CSES - String Reorder Given a string, you want to reorder its characters so that no two adjacent characters are the same. What is the lexicographically minimal such string?

Input

The only input line as a string of length n consisting of characters A–Z.

Output

Print the lexicographically minimal reordered string where no two adjacent characters are the same. If it is not possible to create such a string, print 1.

Constraints
Example

Input:
HATTIVATTI

Output:
AHATITITVT

Stack Weights

CSES - Stack Weights You have n coins, each of which has a distinct weight.

There are two stacks which are initially empty. On each step you move one coin to a stack. You never remove a coin from a stack.

After each move, your task is to determine which stack is heavier (if we can be sure that either stack is heavier).

Input

The first input line has an integer n: the number of coins. The coins are numbered 1,2,,n. You know that coin i is always heavier than coin i1, but you don't know their exact weights.

After this, there are n lines that describe the moves. Each line has two integers c and s: move coin c to stack s (1 = left, 2 = right).

Output

After each move, print < if the right stack is heavier, > if the left stack is heavier, and ? if we can't know which stack is heavier.

Constraints
Example

Input:
3
2 1
3 2
1 1


Output:
>
<
?


Explanation: After the last move, if the coins are [2,3,4], the left stack is heavier, but if the coins are [1,2,5], the right stack is heavier.

Pyramid Array

CSES - Pyramid Array You are given an array consisting of n distinct integers. On each move, you can swap any two adjacent values.

You want to transform the array into a pyramid array. This means that the final array has to be first increasing and then decreasing. It is also allowed that the final array is only increasing or decreasing.

What is the minimum number of moves needed?

Input

The first input line has an integer n: the size of the array.

The next line has n distinct integers x1,x2,,xn: the contents of the array.

Output

Print one integer: the minimum number of moves.

Constraints
Example

Input:
4
2 1 5 3


Output:
1

Explanation: You may swap the first two values which creates a pyramid array [1,2,5,3].

Increasing Subsequence II

CSES - Increasing Subsequence II Given an array of n integers, your task is to calculate the number of increasing subsequences it contains. If two subsequences have the same values but in different positions in the array, they are counted separately.

Input

The first input line has an integer n: the size of the array.

The second line has n integers x1,x2,,xn: the contents of the array.

Output

Print one integer: the number of increasing subsequences modulo 109+7.

Constraints
Example

Input:
3
2 1 3


Output:
5

Explanation: The increasing subsequences are [2], [1], [3], [2,3] and [1,3].

String Removals

CSES - String Removals You are given a string. You can remove any number of characters from it, but you cannot change the order of the remaining characters.

How many different strings can you generate?

Input

The first input line contains a string of size n. Each character is one of a–z.

Output

Print one integer: the number of strings modulo 109+7.

Constraints
Example

Input:
aybabtu

Output:
103

Bit Inversions

CSES - Bit Inversions There is a bit string consisting of n bits. Then, there are some changes that invert one given bit. Your task is to report, after each change, the length of the longest substring whose each bit is the same.

Input

The first input line has a bit string consisting of n bits. The bits are numbered 1,2,,n.

The next line contains an integer m: the number of changes.

The last line contains m integers x1,x2,,xm describing the changes.

Output

After each change, print the length of the longest substring whose each bit is the same.

Constraints
Example

Input:
001011
3
3 2 5


Output:
4 2 3

Explanation: The bit string first becomes 000011, then 010011, and finally 010001.

Xor Pyramid

CSES - Xor Pyramid
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Consider a xor pyramid where each number is the xor of lower-left and lower-right numbers. Here is an example pyramid:

Given the bottom row of the pyramid, your task is to find the topmost number.

Input

The first input line has an integer n: the size of the pyramid.

The next line has n integers a1,a2,,an: the bottom row of the pyramid.

Output

Print one integer: the topmost number.

Constraints
  • 1n2105
  • 1ai109
Example

Input:
8
2 10 5 12 9 5 1 5


Output:
9

Writing Numbers

CSES - Writing Numbers You would like to write a list of positive integers 1,2,3, using your computer. However, you can press each key 09 at most n times during the process.

What is the last number you can write?

Input

The only input line contains the value of n.

Output

Print the last number you can write.

Constraints
Example

Input:
5

Output:
12

Explanation: You can write the numbers 1,2,,12. This requires that you press key 1 five times, so you cannot write the number 13.

String Transform

CSES - String Transform Consider the following string transformation:
  1. append the character # to the string (we assume that # is lexicographically smaller than all other characters of the string)
  2. generate all rotations of the string
  3. sort the rotations in increasing order
  4. based on this order, construct a new string that contains the last character of each rotation
For example, the string babc becomes babc#. Then, the sorted list of rotations is #babc, abc#b, babc#, bc#ba, and c#bab. This yields a string cb#ab.

Input

The only input line contains the transformed string of length n+1. Each character of the original string is one of a–z.

Output

Print the original string of length n.

Constraints
Example

Input:
cb#ab

Output:
babc

Letter Pair Move Game

CSES - Letter Pair Move Game There are 2n boxes in a line. Two adjacent boxes are empty, and all other boxes have a letter "A" or "B". Both letters appear in exactly n1 boxes.

Your task is to move the letters so that all letters "A" appear before any letter "B". On each turn you can choose any two adjacent boxes that have a letter and move the letters to the two adjacent empty boxes, preserving their order.

It can be proven that either there is a solution that consists of at most 10n turns or there are no solutions.

Input

The first line has an integer n: there are 2n boxes.

The second line has a string of 2n characters which describes the starting position. Each character is "A", "B" or "." (empty box).

Output

First print an integer k: the number of turns. After this, print k lines that describe the moves. You can print any solution, as long as k1000.

If there are no solutions, print only "-1".

Constraints
Example 1

Input:
3
AB..BA


Output:
2
ABBA..
A..ABB


Example 2

Input:
3
ABAB..


Output:
-1

Maximum Building I

CSES - Maximum Building I You are given a map of a forest where some squares are empty and some squares have trees.

What is the maximum area of a rectangular building that can be placed in the forest so that no trees must be cut down?

Input

The first input line contains integers n and m: the size of the forest.

After this, the forest is described. Each square is empty (.) or has trees (*).

Input

Print the maximum area of a rectangular building.

Constraints
Example

Input:
4 7
...*.*.
.*.....
.......
......*


Output:
12

Sorting Methods

CSES - Sorting Methods Here are some possible methods using which we can sort the elements of an array in increasing order:
  1. At each step, choose two adjacent elements and swap them.
  2. At each step, choose any two elements and swap them.
  3. At each step, choose any element and move it to another position.
  4. At each step, choose any element and move it to the front of the array.
Given a permutation of numbers 1,2,,n, calculate the minimum number of steps to sort the array using the above methods.

Input

The first input line contains an integer n.

The second line contains n integers describing the permutation.

Output

Print four numbers: the minimum number of steps using each method.

Constraints
Example

Input:
8
7 8 2 6 5 1 3 4


Output:
20 6 5 6

Cyclic Array

CSES - Cyclic Array You are given a cyclic array consisting of n values. Each element has two neighbors; the elements at positions n and 1 are also considered neighbors.

Your task is to divide the array into subarrays so that the sum of each subarray is at most k. What is the minimum number of subarrays?

Input

The first input line contains integers n and k.

The next line has n integers x1,x2,,xn: the contents of the array.

There is always at least one division (i.e., no value in the array is larger than k).

Output

Print one integer: the minimum number of subarrays.

Constraints
Example

Input:
8 5
2 2 2 1 3 1 2 1


Output:
3

Explanation: We can create three subarrays: [2,2,1], [3,1], and [2,1,2] (remember that the array is cyclic).

List of Sums

CSES - List of Sums List A consists of n positive integers, and list B contains the sum of each element pair of list A.

For example, if A=[1,2,3], then B=[3,4,5], and if A=[1,3,3,3], then B=[4,4,4,6,6,6].

Given list B, your task is to reconstruct list A.

Input

The first input line has an integer n: the size of list A.

The next line has n(n1)2 integers: the contents of list B.

You can assume that there is a list A that corresponds to the input, and each value in A is between 1k.

Output

Print n integers: the contents of list A.

You can print the values in any order. If there are more than one solution, you can print any of them.

Constraints
Example

Input:
4
4 4 4 6 6 6


Output:
1 3 3 3

Explanation: In this case list A can be either [1,3,3,3] or [2,2,2,4] and both solutions are accepted.

Increasing Array II

CSES - Increasing Array II You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.

On each move, you can increase or decrease the value of any element by one. What is the minimum number of moves required?

Input

The first input line contains an integer n: the size of the array.

Then, the second line contains n integers x1,x2,,xn: the contents of the array.

Output

Print the minimum number of moves.

Constraints
Example

Input:
5
3 8 5 6 5


Output:
4

Food Division

CSES - Food Division There are n children around a round table. For each child, you know the amount of food they currently have and the amount of food they want. The total amount of food in the table is correct.

At each step, a child can give one unit of food to his or her neighbour. What is the minimum number of steps needed?

Input

The first input line contains an integer n: the number of children.

The next line has n integers a1,a2,,an: the current amount of food for each child.

The last line has n integers b1,b2,,bn: the required amount of food for each child.

Output

Print one integer: the minimum number of steps.

Constraints
Example

Input:
3
3 5 0
2 4 2


Output:
2

Explanation: Child 1 gives one unit of food to child 3, and child 2 gives one unit of food to child 3.

Bit Problem

CSES - Bit Problem Given a list of n integers, your task is to calculate for each element x:
  1. the number of elements y such that xy=x
  2. the number of elements y such that x&y=x
  3. the number of elements y such that x&y0
Input

The first input line has an integer n: the size of the list.

The next line has n integers x1,x2,,xn: the elements of the list.

Output

Print n lines: for each element the required values.

Constraints
Example

Input:
5
3 7 2 9 2


Output:
3 2 5
4 1 5
2 4 4
1 1 3
2 4 4

De Bruijn Sequence

CSES - De Bruijn Sequence

Mail Delivery

CSES - Mail Delivery Your task is to deliver mail to the inhabitants of a city. For this reason, you want to find a route whose starting and ending point are the post office, and that goes through every street exactly once.

Input

The first input line has two integers n and m: the number of crossings and streets. The crossings are numbered 1,2,,n, and the post office is located at crossing 1.

After that, there are m lines describing the streets. Each line has two integers a and b: there is a street between crossings a and b. All streets are two-way streets.

Every street is between two different crossings, and there is at most one street between two crossings.

Output

Print all the crossings on the route in the order you will visit them. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

2n105
1m2.105
1a,bn

Example

Input:
6 8
1 2
1 3
2 3
2 4
2 6
3 5
3 6
4 5


Output:
1 2 6 3 2 4 5 3 1
Your task is to construct a minimum-length bit string that contains all possible substrings of length n. For example, when n=2, the string 00110 is a valid solution, because its substrings of length 2 are 00, 01, 10 and 11.

Input

The only input line has an integer n.

Output

Print a minimum-length bit string that contains all substrings of length n. You can print any valid solution.

Constraints
Example

Input:
2

Output:
00110